题目链接：D. Same GCDs
time limit per test:2 seconds memory limit per test:256 megabytes inputstandard input outputstandard output
You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a x,m). Note: gcd(a,b) is the greatest common divisor of a and b. Input The first line contains the single integer T (1≤T≤50) — the number of test cases. Next T lines contain test cases — one per line. Each line contains two integers a and m (1≤a<m≤1010). Output Print T integers — one per test case. For each test case print the number of appropriate x-s. input
代码语言：javascript复制3
4 9
5 10
42 9999999967output
代码语言：javascript复制6
1
9999999966Note In the first test case appropriate x-s are [0,1,3,4,6,7]. In the second test case the only appropriate x is 0.
题目大意
给你两个数 a，m。从[a，a m)中取出任意一个数x，使得gcd(x,m)=gcd(a,m)成立，问你这样的的x的个数一共有几个。
解题思路
我们设 p=gcd(a,m); 则p=gcd(x,m);然后同时除以p得1=gcd(x/p,m/p);这时候我们发现其实要求的的也就是[a/p,a/p m/p)中与m/p互质的数有几个。同时减去a/p的，也就是[1,m/p)中于m/p互质的的个数，直接用欧拉函数就可以了；
代码
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define ll long long
int main()
{
int t;
ll a,m;
cin>>t;
while(t--)
{
cin>>a>>m;
ll p=__gcd(a,m);
ll ans=m/p;
ll q=ans;
//欧拉函数
for(ll i=2;i*i<=q;i )
{
if(q%i==0) ans=ans-ans/i;
while(q%i==0) q/=i;
}
if(q!=1) ans-=ans/q;
cout<<ans<<"n";
}
return 0;
}
