FML

题解 #

让$g= \gcd(a,m)$，所以我们有$a=g\cdot k，m=g\cdot l,\gcd(l,k)=1$，不难发现，如果我们想要使$\gcd(a,m)=\gcd(a+x,m)$， $x$必须是$g$的倍数，设$x=n\cdot g$。而且，$k+n$和$l$必须要互质，所以我们要找到从$k$到$k+l$中与$l$互质的数的个数。对于那些大于$l$的数，如果 $\gcd(k+x,l)=1$那么$\gcd((k+x)\bmod l,l)=1$。又因为$(k+x)\bmod l< l$，所以我们真正要算的是比$l$小并且与$l$互质的数的个数，也就是$\varphi(l)$。

Code #

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll Phi(ll m){
	ll ans=m;
	for(ll i=2;i*i<=m;i++){
		if(m%i==0){
			ans-=ans/i;
			while(m%i==0) m/=i;
		}
	}
	if(m>1) ans-=ans/m;
	return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int tt;
	cin>>tt;
	while(tt--){
		ll a,m;
		cin>>a>>m;
		cout<<Phi(m/gcd(a,m))<<endl;
 
	}
    return 0;
}