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

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

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

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

链接

计蒜客 30999

题解

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

  1. xx 为素数时,f(x)=2f(x)=2,即 (1,x)(1,x)(x,1)(x,1)
  2. xx 的最小质因子为 pp,且 p\not\mid\frac{x}{p} 时,f(x)=2f(px)f(x)=2f(\frac{p}{x})
  3. xx 的最小质因子为 pp,且 pxpp\mid\frac{x}{p} 时:
    • 如果 pxp2p|\frac{x}{p^2},那么 xxpp 的指数至少为 33,即无论如何划分 (a,b)(a,b),两个数中一定有一个数中 pp 的指数为 22,即不存在合法的划分方案。
    • 否则,xxpp 的指数至少为 22,把这两个 pp 分别分给 (a,b)(a,b) 中的 aabb,剩余的 xp\frac{x}{p} 就是一个子问题了,即 f(x)=f(xp2)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("");
}