AcWing 3999. 最大公约数
原题链接
困难
作者:
最后五分钟
,
2024-04-11 16:23:36
,
所有人可见
,
阅读 8
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int phi(int x)
{
int res=x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)res=res/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)res=res/x*(x-1);
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
int a,m;
cin>>a>>m;
int g=gcd(a,m);
cout<<phi(m/g)<<endl;
}
return 0;
}