Mismo GCD


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Java, Python, VB

Dado dos enteros A y M. Calcula el número de enteros X tal que 0 \leq X < M y gcd(A, M) = gcd(A + X, M).

Nota:

gcd(a, b) es el máximo común divisor de a y b.

Entrada:

La primera linea contiene un entero T (1 \leq T \leq 50) - El número de casos de prueba.

Las siguientes T líneas contienen los casos de prueba, uno por línea. Cada línea contiene dos enteros A y M (1 \leq A < M \leq 10^{10}).

Salida:

Para cada caso de prueba imprime un entero - la cantidad de posibles X-s.

Entrada de ejemplo:

3
4 9
5 10
42 9999999967

Salida de ejemplo 1:

6
1
9999999966

Nota:

En el primer caso de prueba las posibles X-s son \{0, 1, 3, 4, 6, 7\}.

En el segudo la única X es 0.


Comments


  • 2
    josue  commented on Jan. 31, 2022, 10:54 p.m.

    Me gustaría ver la editorial de este problema en q sitio la puedo encontrar?