Codeforces Round 81 Same GCDs

Same GCDs

原文
题意：
给定a,m 求x在 \([0,m)\) 中有多少数字满足 \(gcd(a,m) =gcd(a+x,m)\)

思路：

我们令\(g= gcd (a,m)\)
那么\(a = k_1g\) , \(m=k_2g\),且\(gcd(k_1,k_2) = 1\)

那么问题就变成了在\([a,a+m-1]\) 里面找到一个 x满足 \(x=k_3g, \ \ \ gcd (k_3,k_2)= 1\)

首先 x 需要满足是 g 的倍数，所以问题就变成了在区间 \([\frac{a}{g}, \frac{a + m - 1}{g}]\) 里面找和 k2 互质的数的个数。

然后用容斥原理区间[L,R]中与 k 互质的数的个数的板子即可
代码：

#include<bits/stdc++.h>
#define pii pair<int, int>
#define int long long
using namespace std;
const int N  = 1e3 + 10;
int a[N],num;
void getprime(int x){
    num=0;
    for(int i=2;i*i<=x;i++){
        if( x%i==0){
            a[num++]=i;
            while(x%i==0) 
                x/=i;
        }
    }
    if(x>1)  a[num++]=x;
}
int qu(int r,int x){
    getprime(x);
    int ans=0;
    for(int i=1;i<(1<<num);i++){
        int k=0;
        int mul=1;
        for(int j=0;j<=num;j++){
            if(i& (1<<j)){
                k++;
                mul*=a[j];
            }
        }
        if(k%2) ans+=r/mul;
        else ans-=r/mul;
    }
    if(ans<0) return 0;
    if(r-ans<0) return 0;
    return r - ans;
}
int que(int l,int r,int k){
    return qu(r,k)-qu(l-1,k);
}
int gcd(int a,int b)
{
    int  c=a%b;
    while(c!=0)
    {
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}

void solve(){

    int a, m; cin >> a >> m;
    int g = gcd(a, m);
    int L = a / g, R = (a + m - 1) / g;
    cout<< que(L, R, m / g)<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --)
     solve();
    return 0;
}