欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces - 1295D Same GCDs (欧拉函数,GCD性质)

程序员文章站 2022-07-12 13:51:02
...

???? ???? ????

CodeForces - 1295D Same GCDs (欧拉函数,GCD性质)

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;
}