题意：
给两个整数a,m (( 1 le a < m le 10^{10} ).)
问有多少个x满足 (0 le x < m ,gcd(a, m) = gcd(a + x, m) .)
输出满足上式x的个数
思路：
令p=(gcd(a, m)),
(0 le x < m ,gcd(a, m) = gcd(a + x, m) .)相等的个数等于(1 le x <= m ,gcd(a, m) = gcd( x, m) .)
证明：前提(gcd(a,b) = gcd(b,a mod b))
(0 le x < m ,gcd(a, m) = gcd(a + x, m) .)即(a le k < a+m ,gcd(a, m) = gcd(k, m) .)
[a,a+m),可分成[a,m],[m+1,a+m)
根据前提：[m+1,a+m)和[1,a)的gcd个数应该相等
所以k(in)[a,a+m),(gcd(k,m)==gcd(a,m))即k(in)[1,m],(gcd(k,m)==gcd(a,m))的个数
然后即求(1 le k <= m ,gcd(k/p,m/p)==1)，很明显该值为m/p欧拉函数的值，直接用欧拉函数的模版求即可,O((sqrt(n)))
代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
void solve(ll m){
ll ans=m;
for(ll i=2;i*i<=m;i++){
if(m%i==0){
ans-=(ans/i);
while(m%i==0)m/=i;
}
}
if(m>1)ans-=ans/m;
printf("%lld
",ans);
}
int main()
{
int t;
ll m,a;
scanf("%d",&t);
while(t--){
scanf("%lld %lld",&a,&m);
ll p=gcd(a,m);
m/=p;
solve(m);
}
return 0;
}