传送门：https://www.luogu.org/problemnew/show/P2522

题目描述

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

分析

特殊情况和POI2007 ZAP-Queries相同。
接下来的问题就是解决普遍情况，不难得到答案就是\(ans(b,d)-ans(b,c-1)-ans(a-1,d)+ans(a-1,c-1)\)，这是容斥原理。
这道题目有毒，int和long long乱开会T掉，要注意。

ac代码

#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0; T fl = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') fl = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= fl;
}
#define N 50005
int prime[N], mu[N], sum[N];
bool vis[N];
int a, b, c, d, k, cnt;
void get_mu(int MAXN) {
    mu[1] = 1;
    for (int i = 2; i <= MAXN; i ++) {
        if (!vis[i]) {
            prime[++ cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= MAXN; j ++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
            else mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= MAXN; i ++) sum[i] = sum[i - 1] + mu[i];
}
ll solve(int a, int b) {
    ll res = 0;
    for (int l = 1, r; l <= min(a, b); l = r + 1) {
        r = min(a / (a / l) , b / (b / l));
        res += 1ll * (a / (l * k)) * (b / (l * k)) * (sum[r] - sum[l - 1]);
    }
    return res;
}
int main() {
    int cas;
    read(cas);
    get_mu(50000);
    while (cas --) {
        read(a); read(b); read(c); read(d); read(k);
        printf("%lld\n", solve(b, d) - solve(b, c - 1) - solve(a - 1, d) + solve(a - 1, c - 1));
    }
    return 0;
}

巴特西

[luogu2522][bzoj2301][HAOI2011]Problem b【莫比乌斯反演】

题目描述

分析

ac代码

最新文章

热门文章