题意：

问你 g c d ( a , m ) = g c d ( a + x , m ) gcd(a, m) = gcd(a + x, m) gcd(a,m)=gcd(a+x,m)的话，有多少 x x x满足这种情况？
其中 1 ≤ a , m ≤ 1 0 10 1 ≤ a, m≤10^{10} 1≤a,m≤1010， 0 ≤ x ＜ m 0 ≤ x＜m 0≤x＜m

题解：
令 k = a + x k = a + x k=a+x
令 d = g c d ( a , m ) = g c d ( k , m ) d = gcd(a, m) = gcd(k, m) d=gcd(a,m)=gcd(k,m)
令 a ′ = a / d , m ′ = m / d , k ′ = k / d a' = a / d, m' = m / d, k' = k / d a′=a/d,m′=m/d,k′=k/d

那么可以有 g c d ( a ′ , m ′ ) = g c d ( k ′ , m ′ ) = 1 gcd(a', m') = gcd(k', m') = 1 gcd(a′,m′)=gcd(k′,m′)=1
由欧几里德算法：
g c d ( k ′ , m ′ ) = g c d ( m ′ , k ′ % m ′ ) = 1 gcd(k', m')= gcd(m', k' \% m') = 1 gcd(k′,m′)=gcd(m′,k′%m′)=1

由于 0 ≤ x ＜ m , a ≤ k ≤ a + m 0 ≤ x＜m, a ≤ k ≤ a + m 0≤x＜m,a≤k≤a+m
a ′ ≤ k ′ ＜ a ′ + m ′ a' ≤ k' ＜ a' + m' a′≤k′＜a′+m′
故 k ′ % m ′ ∈ [ a ′ % m ′ <mtext>   </mtext> a ′ % m ′ ) k'\%m' ∈[a'\%m'~a'\%m') k′%m′∈[a′%m′ a′%m′) 即从 0 0 0到 m ′ − 1 m'-1 m′−1.
即问 g c d ( m ′ , t ) = = 1 gcd(m', t) == 1 gcd(m′,t)==1的个数， t ∈ [ 0 , m ′ − 1 ] t∈[0, m'-1] t∈[0,m′−1]
g c d ( m ′ , 0 ) = m ′ gcd(m', 0) = m' gcd(m′,0)=m′
当 t = 1 t = 1 t=1，答案为 1 1 1
否则答案为 [ 1 , m ′ − 1 ] [1, m'-1] [1,m′−1]中，与 m ′ m' m′互质的数的个数
那么显然就是欧拉函数裸题了。