FML

Solution #

Let $g= \gcd(a,m)$, so we have $a=g\cdot k, m=g\cdot l,\gcd(l,k)=1$,first observation is that if we want $\gcd(a,m)=\gcd(a+x,m)$, $x$ has to be a multiple of $g$, let $x=n\cdot g$. Furthermore, $k+n$ and $l$ have to be coprime, so we need to find how many numbers ranging from $k$ to $k+l$ are coprime with $l$. For numbers bigger than $l$, if $\gcd(k+x,l)=1$, then $\gcd((k+x)\bmod l,l)=1$. Since $(k+x)\bmod l< l$, what we actually need to find is the number of numbers that are coprime with $l$ and smaller than $l$, i.e. $\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;
}