#include <bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a,ll m)//辗转相除法求最大公约数 { ll b; while(m%a){ m%=a; b=m,m=a,a=b; } return a; } ll Get_phi(ll n)//欧拉定义法求phi(n) { ll phi=n; for(ll i=2;i*i<=n;i++){ if(n%i==0) { phi*=(i-1.0)/i; while(n%i==0) n/=i*1.0; } } if(n>1) phi*=(n-1.0)/n; return phi; } int main() { #ifndef ONLINE_JUDGE freopen("3999.txt","r",stdin); freopen("out.txt","w",stdout); #endif ll a,m,b; int t; scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%lld%lld",&a,&m); b=gcd(a,m); b=Get_phi(m/b);//题意为求(m/最大公约数)的欧拉值 printf("%lld\n",b); } return 0; }
AcWing 3999. 最大公约数代码实现,今日份学习