计算与 n 最大公约数一定的数的数量

· · 个人记录

如何方便地计算 1\sim m 中与 n 的 \gcd 为 i 的数的数量？

首先，我们求出 n 的所有因数 d_{1\sim k}，设 f_i 表示与 n 的 \gcd 为 d_i 的数的数量，g_i 表示与 n 的 \gcd 为 d_i 倍数的数的数量。我们要求的就是 f_i，则：

g_i=\lfloor \frac m{d_i}\rfloor g_i=\sum_{d_i|d_j}f_j

下面这个式子的原理是，我们枚举与 n 的 \gcd 具体是 d_i 的哪个倍数。

这样，我们可以写出 f_i 的表达式：

f_i=g_i-\sum_{i\ne j,d_i|d_j}f_j

这样，我们从大到小依次算 f，每次枚举 j>i，若 d_i|d_j，就把 f_j 从 g_i 中减去即可。

这样，时间复杂度为 O(d^2(n))，可以解决 10^9 范围内的问题。

vector<int> d,f;
for(int i=1;i*i<=n;i++){
    if(n%i==0){         
        d.push_back(i);
        if(i!=n/i)d.push_back(n/i);
    }
}
sort(d.begin(),d.end());
f.resize(d.size());
for(int i=0;i<d.size();i++)
    f[i]=m/d[i];
for(int i=d.size()-1;i>=0;i--)
    for(int j=d.size()-1;j>i;j--)
        if(d[j]%d[i]==0)
            f[i]-=f[j];