FML
Solution #
Let , so we have ,first observation is that if we want , has to be a multiple of , let . Furthermore, and have to be coprime, so we need to find how many numbers ranging from to are coprime with . For numbers bigger than , if , then . Since , what we actually need to find is the number of numbers that are coprime with and smaller than , i.e. .
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;
}