题目大意
求$gcd(a, m) = gcd(a+x, m), 0 <= x < m, 1 <= a < m <= 10^{10}$的$x$的个数
题解
已知$a < m, 0 <= x < m$,根据最大公约数的性质$a >= b, gcd(a, b)=gcd(a-b,b)$,所以如果$a+x>=m$那么$gcd(a+x,m)=gcd(a+x-m,m)$即$a+x$可以写成$(a+x)\%m$,令$x’=(a+x)\%m,0 <= x’ < m$,则有$(x’,m)=(a,m)$,设$(a,m)=d$那么$(x’,m)=d$,那么$(x’/d, m/d)=1$由于$0 <= x’ < m$,那么$0 <= x’/d < m/d$,答案就是求$φ(m/d)$
1 |
|