CF
题意:
给定数字$a,m(1\le a<m\le10^{10})$,求满足$\gcd(a,m)==\gcd(a+x,m)$的$x(0\le x<m)$的个数。
题解:
首先我们需要一个转化$\gcd(a+x,m)=\gcd(m,(a+x)\%m)=\gcd((a+x)\%m,m)$。
设$\gcd(a,b)=g$,则$\gcd((a+x)\%m,m)=g$。
设$i=(a+x)\%m$,易知$i\in[0,m-1)$。
问题就相当于转化成了求$i$满足$\gcd(i,m)=g$的个数,即$\gcd(\frac{i}{g},\frac{m}{g})=1$的个数。
即小于且与$\frac{m}{g}$互质的数,那不就是欧拉函数吗。
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2021/06/30/CF-1295D/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!