「BZOJ 2820」YY的GCD - 莫比乌斯反演

发表于 | 分类于

求 ， 且 为质数的 数量。

链接

BZOJ 2820

题解

首先，我们只需要处理 的情况，当 的情况只需要交换 和 即可。

设小于 质数为 ，则答案为

根据莫比乌斯反演，我们有

令 ，我们在外层枚举 然后对每个质因子计算

设

考虑线性筛求 的过程，当 时

当 时

线性筛后分块处理即可。

代码

#include <cstdio>
#include <cmath>
#include <vector>

const int MAXT = 10000;
const int MAXN = 10000000;
const int MAXM = 10000000;

bool isNotPrime[MAXN + 1];
int miu[MAXN + 1], f[MAXN + 1], s[MAXN + 1];
std::vector<int> primes;
inline void getPrimes() {
    primes.reserve(MAXN);
    isNotPrime[0] = isNotPrime[1] = true;
    for (int i = 2; i <= MAXN; i++) {
        if (!isNotPrime[i]) {
            primes.push_back(i);
            miu[i] = -1;
            f[i] = 1;
        }
        for (std::vector<int>::const_iterator p = primes.begin(); p != primes.end() && i * *p <= MAXN; p++) {
            isNotPrime[i * *p] = true;
            if (i % *p == 0) {
                miu[i * *p] = 0;
                f[i * *p] = miu[i];
                break;
            } else {
                miu[i * *p] = -miu[i];
                f[i * *p] = miu[i] - f[i];
            }
        }
    }

    for (int i = 1; i <= MAXN; i++) s[i] = s[i - 1] + f[i];
}

inline long long solve(const int n, const int m) {
    long long ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = std::min(n / (n / l), m / (m / l));
        ans += (s[r] - s[l - 1]) * static_cast<long long>(n / l) * static_cast<long long>(m / l);
    }

    return ans;
}

int main() {
    getPrimes();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        if (n > m) std::swap(n, m);
        printf("%lld\n", solve(n, m));
    }

    return 0;
}