Editorial for C3-IC y la hipótesis (CIIC 2021)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

Subtarea 1:

Note que se puede recorrer todos los pares con fuerza bruta y preguntar si son válidos, complejidad $O(T\cdot n^2 \cdot log{n})$ ~O(T\cdot n^2 \cdot log{n})~, $(T\cdot n^3)$ ~(T\cdot n^3)~ o un poco más dependiendo como se calcule el $gcd$ ~gcd~.

Subtarea 2:

Primero note que:

Un par $(i, j)$ ~(i, j)~ es válido si y solo si $gcd(i, n) * gcd(j, n)$ ~gcd(i, n) * gcd(j, n)~ es un divisor de $n$ ~n~.

Note que como el menor primo es mayor que $100$ ~100~, y los números son hasta $10^5$ ~10^5~, $n$ ~n~ solo puede ser:

Un primo, en cuyo caso la respuesta es $\frac{n\cdot{(n+1)}}{2}-1$ ~\frac{n\cdot{(n+1)}}{2}-1~, o sea, todos los pares $(i, j)$ ~(i, j)~ menos $(n, n)$ ~(n, n)~.
La multiplicación de dos primos $p$ ~p~ y $q$ ~q~, en cuyo caso debemos contar todos los pares, y luego descontar los pares $(i, j)$ ~(i, j)~ tal que cumplan una de las siguientes condiciones:
- $gcd(i,n) = p$ ~gcd(i,n) = p~ y $gcd(j,n) = p$ ~gcd(j,n) = p~, estos pares la podemos contar como $(\frac{n}{p}-1) \cdot (\frac{n}{p}-1)$ ~(\frac{n}{p}-1) \cdot (\frac{n}{p}-1)~.
- $gcd(i,n) = q$ ~gcd(i,n) = q~ y $gcd(j,n) = q$ ~gcd(j,n) = q~, los podemos contar de manera similar a los anteriores.
- $gcd(i,n) = p \cdot q$ ~gcd(i,n) = p \cdot q~ y $gcd(j,n) = p$ ~gcd(j,n) = p~, estos los podemos contar como $\frac{n}{p}$ ~\frac{n}{p}~.
- $gcd(i,n) = p \cdot q$ ~gcd(i,n) = p \cdot q~ y $gcd(j,n) = q$ ~gcd(j,n) = q~, estos los podemos contar como $\frac{n}{q}$ ~\frac{n}{q}~.
El cuadrado de un primo $p$ ~p~, aquí podemos contar todos los pares y descontar los que $gcd(i,n) \neq 1$ ~gcd(i,n) \neq 1~ y $gcd(j,n) = n$ ~gcd(j,n) = n~, que podemos hacerlo de manera similar al caso anterior, o como $n - \phi{n}$ ~n - \phi{n}~.

Complejidad $O(T \cdot \sqrt{n})$ ~O(T \cdot \sqrt{n})~ o quizá menos dependiendo de la factorización.

Subtarea 3

Como en esta subtarea $n$ ~n~ es la potencia de un primo podemos contar la cantidad de elementos con $gcd(i, n) = p^x$ ~gcd(i, n) = p^x~ como $\frac{n}{p^x} - \frac{n}{p^{x+1}}$ ~\frac{n}{p^x} - \frac{n}{p^{x+1}}~.

Podemos recorrer los pares $(a, b)$ ~(a, b)~ tal que $p^{a+b}$ ~p^{a+b}~ no divide a $n$ ~n~, y para cada uno de ellos contar la cantidad de pares que tienen $gcd(i,n) = p^a$ ~gcd(i,n) = p^a~ y $gcd(j,n) = p^b$ ~gcd(j,n) = p^b~ como se explica en el texto anterior, así contamos los pares malos y se los restamos al total.

Complejidad $O(T \cdot \sqrt {n} + T \cdot \log^2 n)$ , quizá menos dependiendo de la factorización.

Subtarea 4

Note que:

La cantidad de números $x$ ~x~ tales que $1 \leq x \leq n$ ~1 \leq x \leq n~ y $gcd(x,n) = d$ ~gcd(x,n) = d~ es igual a $\phi{\frac{n}{d}}$ ~\phi{\frac{n}{d}}~ (donde $\phi{m}$ ~\phi{m}~ es la cantidad de números de $1$ ~1~ a $m$ ~m~ coprimos con $m$ ~m~), si y solo si $d$ ~d~ es un divisor de $n$ ~n~, de lo contrario es $0$ ~0~. Esto se puede intuir como si dividiésemos cada elemento del arreglo por $d$ ~d~, los elementos que no sean divisibles no influyen, de los demás nos interesa la cantidad que son iguales a $1$ ~1~, es decir, los coprimos con $\frac{n}{d}$ ~\frac{n}{d}~.

Denotemos como $F(x, y)$ ~F(x, y)~ a la cantidad de pares $(i, j)$ ~(i, j)~ tales que:

$1 \leq i \leq n$ ~1 \leq i \leq n~
$1 \leq j \leq n$ ~1 \leq j \leq n~
$gcd(i, n) = x$ ~gcd(i, n) = x~
$gcd(j, n) = y$ ~gcd(j, n) = y~
$x \neq y$ ~x \neq y~.
$x * y$ ~x * y~ es un divisor de $n$ ~n~.

$F(x, y)$ ~F(x, y)~ puede ser calculado como $\phi{\frac{n}{x}} \cdot \phi{\frac{n}{y}}$ .

Además denotemos $E(x)$ ~E(x)~ como la cantidad de pares $(i, j)$ ~(i, j)~ tales que:

$1 \leq i \leq n$ ~1 \leq i \leq n~
$1 \leq j \leq n$ ~1 \leq j \leq n~
$gcd(i, n) = x$ ~gcd(i, n) = x~
$gcd(j, n) = x$ ~gcd(j, n) = x~
$x^2$ ~x^2~ es un divisor de $n$ ~n~.

$E(x)$ ~E(x)~ puede ser calculado como $\frac{\phi{\frac{n}{x}} \cdot (\phi{\frac{n}{x} + 1)}}{2}$

Ahora $\sum_{x,y \in d(n)} F(x,y)$ ~\sum_{x,y \in d(n)} F(x,y)~ (donde $d(n)$ ~d(n)~ es la lista que contiene a todos los divisores de $n$ ~n~) contaría todos los pares en la respuesta dos veces, excepto los que tienen igual gcd, los cuales serían $\sum_{x \in d(n)} E(x)$ ~\sum_{x \in d(n)} E(x)~, denotemos $f(n)$ ~f(n)~ como $\sum_{x,y \in d(n)} F(x,y)$ ~\sum_{x,y \in d(n)} F(x,y)~ y $g(n)$ ~g(n)~ como $\sum_{x \in d(n)} E(x)$ ~\sum_{x \in d(n)} E(x)~, la respuesta del problema sería $\frac{f(n) + 2\cdot g(n)}{2}$ ~\frac{f(n) + 2\cdot g(n)}{2}~.

En esta subtarea se puede calcular las soluciones chequeando cada par de divisores de cada número y calculando $F(x, y)$ ~F(x, y)~ y $E(x)$ ~E(x)~ como se explica anteriormente.

Puede guardar las soluciones, ya que la suma de la cantidad de divisores de cada número hasta $n$ ~n~ es $O(n\cdot \log n)$ ~O(n\cdot \log n)~ y la cantidad de divisores de un número $n$ ~n~ es $O(n^{\frac{1}{3}})$ ~O(n^{\frac{1}{3}})~.

Complejidad: $O(\sum_{i=1}^{n} d(i)^2)$ ~O(\sum_{i=1}^{n} d(i)^2)~ con baja constante. (donde $d(i)$ ~d(i)~ es la cantidad de divisores del número $i$ ~i~)

Subtarea 5

Se puede notar que las funciones $f$ ~f~ y $g$ ~g~ son multiplicativas, calcular para las potencias de primos similar a la subtarea 3, y para el resto usar el hecho de que son multiplicativas.

El hecho de que $g$ ~g~ sea multiplicativa no es muy importante, ya que se puede calcular en $O(n\log{n})$ ~O(n\log{n})~ sin dificultad, en el caso de $f$ ~f~ si es importante.

Se puede intuir que $f$ ~f~ es multiplicativa, por el hecho de que si separamos el problema en potencias de primos, un par será valido en la multiplicación de las potencias de primos si y solo si es válido en cada una de estas potencias de primos.

Complejidad: $O(n\cdot \log{n})$ ~O(n\cdot \log{n})~ o $O(n)$ ~O(n)~ dependiendo de la implementación.

English version

Subtask 1:

Note that you can go through all the pairs with brute force and ask if they are valid, complexity $O (T \cdot n^2 \cdot \log {n})$ ~O (T \cdot n^2 \cdot \log {n})~, $(T \cdot n^3)$ ~(T \cdot n^3)~ or a little more depending on how the $gcd$ ~gcd~ is calculated.

Subtask 2:

First notice that:

A $(i, j)$ ~(i, j)~ pair is valid if and only if $gcd (i, n) \cdot gcd (j, n)$ ~gcd (i, n) \cdot gcd (j, n)~ is a divisor of $n$ ~n~.

Note that since the lowest prime is greater than $100$ ~100~, and the numbers are up to $10 ^ 5$ ~10 ^ 5~, $n$ ~n~ can only be:

A prime, in which case the answer is $\frac{n \cdot {(n + 1)}}{2} -1$ ~\frac{n \cdot {(n + 1)}}{2} -1~, that is, all pairs $(i, j)$ ~(i, j)~ minus $(n , n)$ ~(n , n)~.
The multiplication of two primes $p$ ~p~ and $q$ ~q~, in which case we must count all the pairs, and then discount the pairs $(i, j)$ ~(i, j)~ such that they meet one of the following conditions:
- $gcd (i, n) = p$ ~gcd (i, n) = p~ and $gcd (j, n) = p$ ~gcd (j, n) = p~, these pairs can be counted as $(\frac {n} {p} -1) \cdot (\frac {n} {p} -1)$ .
- $gcd (i, n) = q$ ~gcd (i, n) = q~ and $gcd (j, n) = q$ ~gcd (j, n) = q~, we can count them in a similar way to the previous ones.
- $gcd (i, n) = p \cdot q$ ~gcd (i, n) = p \cdot q~ and $gcd (j, n) = p$ ~gcd (j, n) = p~, these can be counted as $\frac {n} {p}$ ~\frac {n} {p}~.
- $gcd (i, n) = p \cdot q$ ~gcd (i, n) = p \cdot q~ and $gcd (j, n) = q$ ~gcd (j, n) = q~, we can count these as $\frac {n} {q}$ ~\frac {n} {q}~.
The square of a prime $p$ ~p~, here we can count all the pairs and subtstract those that $gcd (i, n) \neq 1$ ~gcd (i, n) \neq 1~ and $gcd (j, n) = n$ ~gcd (j, n) = n~, which we can do in a similar way to the previous case, or as $n - \phi {n}$ ~n - \phi {n}~.

Complexity $O (T \cdot \sqrt {n})$ ~O (T \cdot \sqrt {n})~ or maybe less depending on the factorization.

Subtask 3

In this subtask $n$ ~n~ is the power of a prime, using that fact we can count the number of elements with $gcd (i, n) = p ^ x$ ~gcd (i, n) = p ^ x~ as $\frac{n}{p^x} - \frac{n}{p^{x+1}}$ ~\frac{n}{p^x} - \frac{n}{p^{x+1}}~.

We can go through the pairs $(a, b)$ ~(a, b)~ such that $p ^ {a + b}$ ~p ^ {a + b}~ does not divide $n$ ~n~, and for each of them count the number of pairs that have $gcd (i, n) = p ^ a$ ~gcd (i, n) = p ^ a~ ans $gcd (j, n) = p ^ b$ ~gcd (j, n) = p ^ b~ as explained in the previous text, so we count the bad pairs and subtract them from the total.

Complexity $O(T \cdot \sqrt {n} + T \cdot \log^2 n)$ , maybe less depending on the factorization.

Subtask 4

It can be shown that:

The quantity of numbers $x$ ~x~ such that $1 \leq x \leq n$ ~1 \leq x \leq n~ and $gcd (x, n) = d$ ~gcd (x, n) = d~ is equal to $\phi {\frac {n} {d}}$ ~\phi {\frac {n} {d}}~ (here $\phi {m}$ ~\phi {m}~ is the quantity of numbers from $1$ ~1~ to $m$ ~m~ which are coprime with $m$ ~m~), if and only if $d$ ~d~ is a divisor of $n$ ~n~, otherwise it is $0$ ~0~. This can be thought as if we divided each element by $d$ ~d~, those that are not divisible doesn't matter, we are interested in those that are equal to $1$ ~1~, which are coprime with $\frac{n}{d}$ ~\frac{n}{d}~.

Let us denote as $F (x, y)$ ~F (x, y)~ the number of pairs $(i, j)$ ~(i, j)~ such that:

$1 \leq i \leq n$ ~1 \leq i \leq n~
$1 \leq j \leq n$ ~1 \leq j \leq n~
$gcd (i, n) = x$ ~gcd (i, n) = x~
$gcd (j, n) = y$ ~gcd (j, n) = y~
$x \neq y$ ~x \neq y~.
$x \cdot y$ ~x \cdot y~ is a divisor of $n$ ~n~.

$F (x, y)$ ~F (x, y)~ can be calculated as $\phi {\frac {n} {x}} \cdot \phi {\frac {n} {y}}$ .

Furthermore, let's denote $E (x)$ ~E (x)~ as the number of pairs $(i, j)$ ~(i, j)~ such that:

$1 \leq i \leq n$ ~1 \leq i \leq n~
$1 \leq j \leq n$ ~1 \leq j \leq n~
$gcd (i, n) = x$ ~gcd (i, n) = x~
$gcd (j, n) = x$ ~gcd (j, n) = x~
$x ^ 2$ ~x ^ 2~ is a divisor of $n$ ~n~.

$E (x)$ ~E (x)~ can be calculated as $\frac {\phi {\frac {n} {x}} \cdot (\phi {\frac {n} {x} + 1)}} {2}$

Now $\sum_{x, y \in d (n)} F (x, y)$ ~\sum_{x, y \in d (n)} F (x, y)~ (here $d (n)$ ~d (n)~ is the list that contains all the divisors of $n$ ~n~) would count all the pairs in the answer twice, except for those that have the same gcd, which would be $\sum_{x \in d (n)} E (x)$ ~\sum_{x \in d (n)} E (x)~, let's denote $f (n)$ ~f (n)~ as $\sum_{x, y \in d (n)} F (x, y)$ ~\sum_{x, y \in d (n)} F (x, y)~ and $g (n)$ ~g (n)~ as $\sum_ {x \in d (n)} E (x)$ ~\sum_ {x \in d (n)} E (x)~, the answer to the problem would be $\frac {f (n) + 2 \cdot g (n)} {2}$ ~\frac {f (n) + 2 \cdot g (n)} {2}~.

In this subtask you can calculate the solutions simply by checking each pair of divisors of each number and calculating $F (x, y)$ ~F (x, y)~ and $E (x)$ ~E (x)~ as explained above.

You can save the solutions, since the sum of the number of divisors of each number up to $n$ ~n~ is $(n \cdot \log n)$ ~(n \cdot \log n)~ and the number of divisors of a number $n$ ~n~ is $O (n ^ {\frac {1} {3}})$ ~O (n ^ {\frac {1} {3}})~.

Complexity: $O (\sum_{i = 1}^{n} d(i) ^ 2)$ ~O (\sum_{i = 1}^{n} d(i) ^ 2)~ with a low constraint. (here $d (i)$ ~d (i)~ is the number of divisors of the number $i$ ~i~)

Subtask 5

It can be shown that the functions $g$ ~g~ and $h$ ~h~ are multiplicative, compute them for the powers of primes similar to subtask 3, and for the rest use the fact that they are multiplicative.

The fact that $h$ ~h~ is multiplicative is not very important, since it can be computed in $O (n \log {n})$ ~O (n \log {n})~ without any trouble without noticing that is multiplicative, but the fact that $g$ ~g~ is multiplicative is important.

It can be shown that $g$ ~g~ is multiplicative, due to the fact that if we separate the problem into powers of primes, a pair will be valid in the multiplication of the powers of primes if and only if it is valid in each of these powers of primes.

Complexity: $O (n \cdot \log {n})$ ~O (n \cdot \log {n})~ or $O (n)$ ~O (n)~ depending on the implementation.

Comments

There are no comments at the moment.