P2522 [HAOI2011]Problem b (莫比乌斯反演)

题目

P2522 [HAOI2011]Problem b

解析：

具体推导过程同P3455 [POI2007]ZAP-Queries
不同的是，这个题求的是\(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)=k\)
像二维前缀和一样容斥一下，输出就完了。

根据luogu某大佬的说法

开longlong的话会TLE。。

代码

//莫比乌斯反演 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int t, n, m, num, k;
int mu[N], p[N], sum[N];
bool vis[N];

template<class T>inline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}

void get_mu(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) p[++num] = i, mu[i] = -1;
        for (int j = 1; j <= num; ++j) {
            if (i * p[j] > n) break;
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            } else mu[i * p[j]] = -mu[i];
        }
    }
}

int cal(int x, int y, int k) {
    int mx = min(x, y), ans = 0;
    for (int l = 1, r; l <= mx; l = r + 1) {
        r = min(x / (x / l), y / (y / l));
        ans += ((x / (l * k)) * (y / (l * k)) * (sum[r] - sum[l - 1]));
    }
    return ans;
}

int a, b, c, d;

signed main() {
    get_mu(N);
    for (int i = 1; i <= N; ++i) sum[i] = sum[i - 1] + mu[i];
    read(t);
    while (t --) {
        read(a), read(b), read(c), read(d), read(k);
        printf("%d\n", cal(b, d, k) - cal(b, c - 1, k) - cal(a - 1, d, k) + cal(a - 1, c - 1, k));
    }
    return 0;
}