题解：CF1295D Same GCDs

· · 题解

引理：设 d 是 a,b 的一个公因数，a=t_1d，b=t_2d，那么 \gcd(a,b)=d 当且仅当 \gcd(t_1,t_2)=1。

证明显然。

同理，对于本题我们先令 d=\gcd(a,m)，将 a 和 m 表示成 d 的倍数的形式。那么原问题转化成了 [a,a+m-1] 里有多少个 d 的倍数除以 d 之后与 \frac{m}{d} 互质，而这些 d 的倍数除以 d 之后显然是一段连续的数。

转化成了一个经典问题：[1,n] 内有多少个数与 x 互质（区间的话差分下就行）。

这个问题有一种容斥做法，我们先补集转换成有多少个数与 x 不互质，那么就相当于求有多少个数与 x 有至少一个公共质因子，直接大力容斥即可，容斥系数为 (-1)^{\text 公共质因子数+1}。

展示下这部分代码：

int calc(int n, int x){
    if(!n) return 0;
    vector<int> vec;
    for(int i = 2; i * i <= x; i++){
        if(x % i) continue;
        int siz = vec.size() - 1;
        For(j, 0, siz) vec.push_back(-vec[j] * i);
        while(!(x % i)) x /= i;
        vec.push_back(i);
    }
    if(x > 1){
        int siz = vec.size() - 1;
        For(j, 0, siz) vec.push_back(-vec[j] * x);
        vec.push_back(x);
    }
    int res = 0;
    for(int v : vec) res += n / v;
    return n - res;
}

这块复杂度应该是 O(\sqrt n+2^{\omega (n)})。

提交记录