题目大意
求$gcd(a, m) = gcd(a x, m), 0 <= x < m, 1 <= a < m <= 10^{10}$的$x$的个数
题解
已知$a < m, 0 <= x < m$，根据最大公约数的性质$a >= b, gcd(a, b)=gcd(a-b,b)$，所以如果$a x>=m$那么$gcd(a x,m)=gcd(a x-m,m)$即$a x$可以写成$(a x)%m$，令$x’=(a x)%m,0 <= x’ < m$，则有$(x’,m)=(a,m)$，设$(a,m)=d$那么$(x’,m)=d$，那么$(x’/d, m/d)=1$由于$0 <= x’ < m$，那么$0 <= x’/d < m/d$，答案就是求$φ(m/d)$
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
int T;
LL a,m;
void solve(){
cin >> a >> m;
LL n = m/__gcd(a, m);
LL ans = n;
for(int i = 2; i <= n/i; i){
if(n%i == 0){
ans = ans / i * (i - 1);
while(n % i == 0) n /= i;
}
}
if(n > 1) ans = ans / n * (n - 1);
cout << ans << endl;
}
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--) solve();
return 0;
}
