acwing P3999最大公约数

实际上，类似于243和245的最大公约数是8；而2443和2445最大公约数是32；两个数的最大公约数就是所有的公约数乘积。那么，题意最大公约数不变就可以转换成两个数虽然在变化，但是他们的公约数没有变化，没有产生新的公约数，就是互质。由此可以直接用欧拉函数计算变化过程中互质的个数即可。 数学推导：设gcd(a,m) = gcd(a+x,m) = d 因为 d|a , d|(a+x) ,d|m ( |是整除符号） 所以 d|x,均可被整除。 将 g c d ( a + x , m ) = d gcd(a+x,m) = d gcd(a+x,m)=d中数全部除以其最大公约数 d 得 g c d ( a ′ + x ′ , m ′ ) = 1 gcd(a'+x',m') = 1 gcd(a′+x′,m′)=1互质

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL mygcd(LL a, LL b)
{
    if(b==0) return a;
    else return mygcd(b,a%b);
}//辗转相除法求最大公约数


LL phi(LL n)
{
    // 欧拉函数求互质个数
    LL res = n;
    for(int i=2; i<=n/i; ++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);
        LL d = mygcd(a,m);
        m/=d;
        cout << phi(m) << endl;
        
    }
    return 0;
}