AcWing 第21场周赛 最大公约数
学习笔记
[令 d=gcd(a,m)=gcd(a+x, m) \
d|a quad d|m quad d|(a+x) ，可得 d|x \
令 a' = frac{a}{d} quad m' = frac{m}{d} quad x' = frac{x}{d} \
去除公约数，则gcd(a'+x', m')=1 \
0 le x < m可得0 le x' < m' \
问题转化为a'+x'在[a', a'+m')有多少个数与m'互质 \
[0,a') mod m'等同于[m',a'+m') mod m' \
[0,a')+[a',m') 即[0, m')等同于[a',m']+[m',a'+m')即[a',a'+m') \
问题转为在[0, m')内有多少个数与m'互质 \
即求m'的欧拉函数
]