Mismo GCD

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 256M

Authors:

FrankHG, Albe, mdario

Problem type

Allowed languages

C, C++, Java, Python, VB

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

Nota:

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

Entrada:

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

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

Salida:

Para cada caso de prueba imprime un entero - la cantidad de posibles $X$ ~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$ ~X~-s son $\{0, 1, 3, 4, 6, 7\}$ ~\{0, 1, 3, 4, 6, 7\}~.

En el segudo la única $X$ ~X~ es $0$ ~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?