CodeForces - 1295D Same GCDs (欧拉函数,GCD性质)
程序员文章站
2022-07-12 13:51:02
...
inline ll eular(ll n)
{
ll ans=n;
for(int i=2; 1ll*i*i<= n; i++)
{
if(n%i==0)
{
ans-=ans/i;
while(n%i==0) n/=i;
}
}
if(n>1) ans-=ans/n;
return ans;
}
ll gcd(ll a,ll b){ return b==0?a : gcd(b,a%b);}
signed main()
{
int T;cin>>T;
while(T--)
{
ll a,m;
cin>>a>>m;
cout<<eular(m/gcd(m,a))<<endl;
}
return 0;
}