Educational Codeforces Round 81 (Rated for Div. 2) D.Same GCDs

题意：

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

题解：
令 $k=a+x$k=a+x
令 $d=gcd(a,m)=gcd(k,m)$d=gcd(a,m)=gcd(k,m)
令 $a^{\prime }=a/d,m^{\prime }=m/d,k^{\prime }=k/d$a′=a/d,m′=m/d,k′=k/d

那么可以有 $gcd(a^{\prime },m^{\prime })=gcd(k^{\prime },m^{\prime })=1$gcd(a′,m′)=gcd(k′,m′)=1
由欧几里德算法：
$gcd(k^{\prime },m^{\prime })=gcd(m^{\prime },k^{\prime }\%m^{\prime })=1$gcd(k′,m′)=gcd(m′,k′%m′)=1

由于 $0\le x＜m,a\le k\le a+m$0≤x＜m,a≤k≤a+m
$a^{\prime }\le k^{\prime }＜a^{\prime }+m^{\prime }$a′≤k′＜a′+m′
故 $k^{\prime }\%m^{\prime }\in \left[a^{\prime }\%m^{\prime }{a}^{\prime }\%m^{\prime }\right)$k′%m′∈[a′%m′ a′%m′) 即从 $0$0到 $m^{\prime }-1$m′−1.
即问 $gcd(m^{\prime },t)==1$gcd(m′,t)==1的个数， $t\in [0,m^{\prime }-1]$t∈[0,m′−1]
$gcd(m^{\prime },0)=m^{\prime }$gcd(m′,0)=m′
当 $t=1$t=1，答案为 $1$1
否则答案为 $[1,m^{\prime }-1]$[1,m′−1]中，与 $m^{\prime }$m′互质的数的个数
那么显然就是欧拉函数裸题了。