题目链接：https://codeforces.com/contest/1295/problem/D
题目大意：
多样例
给你一个a和m。问有多少个x(0<=x<m) 使得gcd(a, m)=gcd(a+x, m)。

思路一：根据扩欧定理：
gcd（a+x, m）= gcd（(a+x)%m, m）
(a+x)%m的取值可能是[0， m-1]。
gcd（a+x, m）= gcd（a, m）
1：如果gcd(a, m)=1。那么就是求gcd(X, m)=1 (0<=X<m) X=0不满足。就是m的欧拉函数。
2：如果GCD=gcd(a, m)!=1。那么就是求gcd(X/GCD, m/GCD)=1 (0/GCD<=X/GCD<m/GCD) X=0/GCD不满足。就是m/GCD 的欧拉函数。

思路二：求gcd(X/GCD, m/GCD)=1
令：F( c ) = gcd(X/GCD, m/GCD)=c的x的取值个数。也就是F( c ) = gcd(X, m/GCD)=c*CGD的个数。

我们求F(1)：
F( c ) c可能的取值是c所有的因子
所有 F( c ) 的和为m。因为X可能的取值范围是[0, m)

我们用容斥定理：

那么圆圈外就是F(1)
而圆圈内就用容斥定理,筛出所有m/GCD的素因子：

法一：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
LL euler(LL n)
{
    LL res=n;
    for(LL i=2;i*i<=n;i++)
    {
        if(n%i==0)//第一次找到的必为素因子
            res=res/i*(i-1);
        while(n%i==0)//把该素因子全部约掉
            n/=i;
    }
    if(n>1)
        res=res/n*(n-1);
 
    return res;
}
 
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        LL a, m;
        scanf("%lld%lld", &a, &m);
        if(__gcd(a,m)==1){
            printf("%lld\n", euler(m));
        }
        else{
            printf("%lld\n", euler(m/__gcd(a, m)));
        }
    }
    return 0;
}

法二：
#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<LL> v;
LL ans=0;

/*c=GCD p=奇加偶减 [L, R] x的取值区间*/
void dfs(int i, LL GCD, int p, LL L, LL R){

    if(i==v.size()){

        ans+=(R/GCD-L/GCD)*p;
        return ;
    }

    dfs(i+1, GCD, p, L, R);//不选择
    dfs(i+1, GCD*v[i], -p, L, R);//选择
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        LL a, m, M;
        v.clear();
        scanf("%lld%lld", &a, &M);
        LL GCD=__gcd(a, M);
        m=M/GCD;
        /*筛出素因子*/
        for(LL i=2; i*i<=m; i++){
            if(m%i==0){
                v.push_back(i);
                while(m%i==0){
                    m/=i;
                }
            }
        }
        if(m!=1){
            v.push_back(m);
        }
        /*容斥*/
        ans=0;
        dfs(0, GCD, 1, a-1, a+M-1);

        printf("%lld\n", ans);
    }

    return 0;
}