思路
引理:若 $d \mid a, d \mid b$,则 $d \mid (ax + by)$,其中 $d, a, b, x, y$ 都是整数。
记 $d = gcd(a, m) = gcd(a + x, m)$,则 $d \mid a, d \mid m, d \mid (a + x)$,则 $d \mid (-a + (a + x))$,即 $d \mid x$。
记 $a^\prime = a / d, m^\prime = m / d, x^\prime = x / d$,则 $gcd(a^\prime + x^\prime, m^\prime) = 1$。
由于 $x \in [0, m)$,因此 $(a + x) \in [a, a + m)$,则 $(a^\prime + x^\prime) \in [a^\prime, a^\prime + m^\prime)$。原问题等价于求区间 $[a^\prime, a^\prime + m^\prime)$ 上有多少个数与 $m^\prime$ 互质。
由于 $a < m$,因此 $a^\prime < m^\prime$。
|-----o------|-----o------
0 a' m' a' + m'
由于在模 $m^\prime$ 的意义下,$0, 1, 2, \cdots, a^\prime - 1$ 等价于 $m^\prime, m^\prime + 1, m^\prime + 2, \cdots, m^\prime + a^\prime - 1$,因此区间 $[m^\prime, a^\prime + m^\prime)$ 上与 $m^\prime$ 互质的数的个数等于区间 $[0, a^\prime)$ 上与 $m^\prime$ 互质的数的个数。因此区间 $[a^\prime, a^\prime + m^\prime)$ 上与 $m^\prime$ 互质的数的个数等于区间 $[0, m^\prime)$ 上与 $m^\prime$ 互质的数的个数,后者就是欧拉函数的定义。
补充:对于任意等价区间,其内每个数模 $m^\prime$ 的值各不相同,即 $\forall_{x, y} \in [m^\prime, m^\prime + a^\prime)$,$x \bmod m^\prime \ne y \bmod m^\prime$,而 $x \bmod m^\prime, y \bmod m^\prime \in [0, a^\prime)$。因此对于任意等价区间,如果它内部某个数 $x$ 与 $m^\prime$ 互质,它在 $[0, a^\prime)$ 中的对应元素是 $x \bmod m^\prime$也与 $m^\prime$ 互质(欧几里得算法),并且同一等价区间内其它与 $m^\prime$ 互质的数 $y$ 在 $[0, a^\prime)$ 中的对应元素是 $y \bmod m^\prime$ 一定不等于 $x \bmod m^\prime$,即等价区间之间互质的数存在一一对应关系。
时间复杂度 $O(T \sqrt m)$。
from math import gcd
def phi(n):
r = n
i = 2
while i <= n // i:
if n % i == 0:
while n % i == 0:
n //= i
r -= r // i
i += 1
if n > 1: r -= r // n
return r
for _ in range(int(input())):
a, m = map(int, input().split())
print(phi(m // gcd(a, m)))