「HAOI2011」Problem b - 莫比乌斯反演

对于给出的 个询问，每次求有多少个数对 ，满足 ，，且 ，函数为 和 的最大公约数。

链接

BZOJ 2301
COGS 548

题解

问题为：求

设

根据容斥原理，答案即为

现在的问题就是求出 函数的值

设

构造函数

由莫比乌斯反演得

这时候我们已经可以暴力计算 了

int ans = 0;
for (int d = 1; d <= (n / k); d++) {
    ans += mu[d] * (n / (k * d)) * (m / (k * d));
}

但是这样的复杂度还是会超时的，我们考虑分块计算。

注意到我们的代码中多次出现了形如 的式子，考虑构造一个新函数

此时的 已经可以分块计算了，通过预处理 的前缀和，我们可以在 的时间内回答一组询问。

代码

#include <cstdio>
#include <algorithm>

const int MAXT = 50000;
const int MAXN = 50000;
const int MAXK = 50000;

bool isNotPrime[MAXN + 1];
int mu[MAXN + 1], s[MAXN + 1], primes[MAXN + 1], cnt;
inline void getPrimes() {
    isNotPrime[0] = isNotPrime[1] = true;
    mu[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (!isNotPrime[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
        }

        for (int j = 0; j < cnt; j++) {
            int t = i * primes[j];
            if (t > MAXN) break;
            isNotPrime[t] = true;
            if (i % primes[j] == 0) {
                mu[t] = 0;
                break;
            } else mu[t] = -mu[i];
        }
    }

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

inline int gcd(const int a, const int b) { return !b ? a : gcd(b, a % b); }

inline int solve(int n, int m, const int k) {
    if (n > m) std::swap(n, m);
    n /= k, m /= k;
    int 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]) * ((n / l) * (m / l));
    }

    return ans;

    /*int ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (gcd(i, j) == k) ans++;
    return ans;*/

    /*int ans = 0;
    for (int d = 1; d <= (n / k); d++) {
        ans += mu[d] * (n / (k * d)) * (m / (k * d));
    }*/
    // printf("solve(%d, %d, %d) = %d\n", n, m, k, ans);
    return ans;
}

inline int solve(const int a, const int b, const int c, const int d, const int k) {
    return solve(b, d, k) - solve(a - 1, d, k) - solve(b, c - 1, k) + solve(a - 1, c - 1, k);
}

int main() {
    getPrimes();
    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b, c, d, k;
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
        printf("%d\n", solve(a, b, c, d, k));
    }

    return 0;
}