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

定义 为满足以下条件的有序二元组 的方案数（即 与 被认为是不同的方案）：

1. ；
2. 和 均为无平方因子数（即其因子中没有除 以外的完全平方数）。

求 ，。

链接

计蒜客 30999

题解

显然， 是积性函数，考虑线性筛。

1. 当 为素数时，，即 与 ；
2. 当 的最小质因子为 ，且 时，；
3. 当 的最小质因子为 ，且 时：
   • 如果 ，那么 中 的指数至少为 ，即无论如何划分 ，两个数中一定有一个数中 的指数为 ，即不存在合法的划分方案。
   • 否则， 中 的指数至少为 ，把这两个 分别分给 中的 和 ，剩余的 就是一个子问题了，即 。

代码

#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("");
}