欧拉函数与辗转相除法结合 8.1@亿万星辰 AcWing 3999

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