CF1295D Same GCDs

樱雪喵 · 2022-07-15 20:19:02 · 题解

前置知识：

• 辗转相除法
• 欧拉函数

首先，根据辗转相除法求 \gcd 的公式，可得 \gcd(a+x,m)=\gcd((a+x)\mod m,m)。
则题目可以转化为：求有多少 x 满足 \gcd(x,m)=\gcd(a,m)，设 \gcd(a,m) 等于定值 k。
等式两边同时除以 k，得 \gcd(\dfrac{x}{k},\dfrac{m}{k})=1。即求与 \dfrac{m}{k} 互质的数的个数，根据欧拉函数的定义知答案为 \varphi(\dfrac{m}{k})。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a,m;
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&a,&m);
        int n=m/__gcd(a,m);
        int ans=n;
        for(int i=2;i*i<=n;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;
    }
    return 0;
}