[令 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') bmod m'等同于[m',a'+m') bmod m' \ [0,a')+[a',m') 即[0, m')等同于[a',m']+[m',a'+m')即[a',a'+m') \ 问题转为在[0, m')内有多少个数与m'互质 \ 即求m'的欧拉函数 ]