「2018 南京网络预赛」Sum - 线性筛

定义 f(x) 为满足以下条件的有序二元组 (a,b) 的方案数(即 (a,b) (b,a) 被认为是不同的方案):

  1. x=ab
  2. a b 均为无平方因子数(即其因子中没有除 1 以外的完全平方数)。

\sum\limits_{i=1}^nf(i) n\leq 2\times 10^7

链接

计蒜客 30999

题解

显然, f(n)=\sum\limits_{d|n}|\mu(d)\mu(\frac{n}{d})| 是积性函数,考虑线性筛。

  1. x 为素数时, f(x)=2 ,即 (1,x) (x,1)
  2. x 的最小质因子为 p ,且 p\not\mid\frac{x}{p} 时, f(x)=2f(\frac{p}{x})
  3. x 的最小质因子为 p ,且 p\mid\frac{x}{p} 时:
    • 如果 p|\frac{x}{p^2} ,那么 x p 的指数至少为 3 ,即无论如何划分 (a,b) ,两个数中一定有一个数中 p 的指数为 2 ,即不存在合法的划分方案。
    • 否则, x p 的指数至少为 2 ,把这两个 p 分别分给 (a,b) 中的 a b ,剩余的 \frac{x}{p} 就是一个子问题了,即 f(x)=f(\frac{x}{p^2})

代码

#include <cstdio>
// #include <vector>

const int MAXN = 2e7;

bool isNotPrime[MAXN + 1];
int primes[MAXN + 1], primeCnt;
int f[MAXN + 1];

inline void sieve() {
    f[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (!isNotPrime[i]) {
            primes[++primeCnt] = i;
            f[i] = 2;
        }

        for (int j = 1; j <= primeCnt && (long long)i * primes[j] <= MAXN; j++) {
            isNotPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                f[i * primes[j]] = (i / primes[j] % primes[j] == 0) ? 0 : f[i] / 2;
                break;
            } else {
                f[i * primes[j]] = f[i] * 2;
            }
        }
    }
}

inline bool isSquareFree(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            x /= i;
            if (x % i == 0) return false;
        }
    }
    return true;
}

int main() {
    sieve();
    static int s[MAXN + 1];
    for (int i = 1; i <= MAXN; i++) s[i] = s[i - 1] + f[i];

    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", s[n]);
    }

    // // int cnt = 0;
    // std::vector<int> v;
    // for (int i = 1; i <= 10000; i++) {
    //     if (isSquareFree(i)) v.push_back(i);
    //     // if (i % int(1e6) == 0) printf("%d: %d\n", i, cnt);
    // }
    // // printf("%d\n", cnt);

    // static int g[10000];
    // for (int i = 0; i < (int)v.size(); i++) {
    //     for (int j = 0; j < (int)v.size(); j++) {
    //         int x = v[i] * v[j];
    //         if (x < 10000) g[x]++;
    //     }
    // }

    // for (int i = 1; i < 10000; i++) {
    //     if (f[i] != g[i]) printf("f[%d] = %d, g[%d] = %d\n", i, f[i], i, g[i]);
    // }

    // int s = 0;
    // for (int i = 1; i < 100; i++) printf("%d, ", s += f[i]);
    // puts("");
}