Subtarea 1:
Note que se puede recorrer todos los pares con fuerza bruta y preguntar si son válidos, complejidad
,
o un poco más dependiendo como se calcule el
.
Subtarea 2:
Primero note que:
- Un par
es válido si y solo si
es un divisor de
.
Note que como el menor primo es mayor que
, y los números son hasta
,
solo puede ser:
Un primo, en cuyo caso la respuesta es
, o sea, todos los pares
menos
.
La multiplicación de dos primos
y
, en cuyo caso debemos contar todos los pares, y luego descontar los pares
tal que cumplan una de las siguientes condiciones:
y
, estos pares la podemos contar como
.
y
, los podemos contar de manera similar a los anteriores.
y
, estos los podemos contar como
.
y
, estos los podemos contar como
.
El cuadrado de un primo
, aquí podemos contar todos los pares y descontar los que
y
, que podemos hacerlo de manera similar al caso anterior, o como
.
Complejidad
o quizá menos dependiendo de la factorización.
Subtarea 3
Como en esta subtarea
es la potencia de un primo podemos contar la cantidad de elementos con
como
.
Podemos recorrer los pares
tal que
no divide a
, y para cada uno de ellos contar la cantidad de pares que tienen
y
como se explica en el texto anterior, así contamos los pares malos y se los restamos al total.
Complejidad
, quizá menos dependiendo de la factorización.
Subtarea 4
Note que:
- La cantidad de números
tales que
y
es igual a
(donde
es la cantidad de números de
a
coprimos con
), si y solo si
es un divisor de
, de lo contrario es
. Esto se puede intuir como si dividiésemos cada elemento del arreglo por
, los elementos que no sean divisibles no influyen, de los demás nos interesa la cantidad que son iguales a
, es decir, los coprimos con
.
Denotemos como
a la cantidad de pares
tales que:



.
es un divisor de
.
puede ser calculado como
.
Además denotemos
como la cantidad de pares
tales que:



es un divisor de
.
puede ser calculado como 
Ahora
(donde
es la lista que contiene a todos los divisores de
) contaría todos los pares en la respuesta dos veces, excepto los que tienen igual gcd, los cuales serían
, denotemos
como
y
como
, la respuesta del problema sería
.
En esta subtarea se puede calcular las soluciones chequeando cada par de divisores de cada número y calculando
y
como se explica anteriormente.
Puede guardar las soluciones, ya que la suma de la cantidad de divisores de cada número hasta
es
y la cantidad de divisores de un número
es
.
Complejidad:
con baja constante. (donde
es la cantidad de divisores del número
)
Subtarea 5
Se puede notar que las funciones
y
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
sea multiplicativa no es muy importante, ya que se puede calcular en
sin dificultad, en el caso de
si es importante.
Se puede intuir que
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
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
,
or a little more depending on how the
is calculated.
Subtask 2:
First notice that:
- A
pair is valid if and only if
is a divisor of
.
Note that since the lowest prime is greater than
, and the numbers are up to
,
can only be:
A prime, in which case the answer is
, that is, all pairs
minus
.
The multiplication of two primes
and
, in which case we must count all the pairs, and then discount the pairs
such that they meet one of the following conditions:
and
, these pairs can be counted as
.
and
, we can count them in a similar way to the previous ones.
and
, these can be counted as
.
and
, we can count these as
.
The square of a prime
, here we can count all the pairs and subtstract those that
and
, which we can do in a similar way to the previous case, or as
.
Complexity
or maybe less depending on the factorization.
Subtask 3
In this subtask
is the power of a prime, using that fact we can count the number of elements with
as
.
We can go through the pairs
such that
does not divide
, and for each of them count the number of pairs that have
ans
as explained in the previous text, so we count the bad pairs and subtract them from the total.
Complexity
, maybe less depending on the factorization.
Subtask 4
It can be shown that:
- The quantity of numbers
such that
and
is equal to
(here
is the quantity of numbers from
to
which are coprime with
), if and only if
is a divisor of
, otherwise it is
. This can be thought as if we divided each element by
, those that are not divisible doesn't matter, we are interested in those that are equal to
, which are coprime with
.
Let us denote as
the number of pairs
such that:




.
is a divisor of
.
can be calculated as
.
Furthermore, let's denote
as the number of pairs
such that:




is a divisor of
.
can be calculated as 
Now
(here
is the list that contains all the divisors of
) would count all the pairs in the answer twice, except for those that have the same gcd, which would be
, let's denote
as
and
as
, the answer to the problem would be
.
In this subtask you can calculate the solutions simply by checking each pair of divisors of each number and calculating
and
as explained above.
You can save the solutions, since the sum of the number of divisors of each number up to
is
and the number of divisors of a number
is
.
Complexity:
with a low constraint. (here
is the number of divisors of the number
)
Subtask 5
It can be shown that the functions
and
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
is multiplicative is not very important, since it can be computed in
without any trouble without noticing that is multiplicative, but the fact that
is multiplicative is important.
It can be shown that
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:
or
depending on the implementation.
Comments