P2522 Problem b

莫反+容斥入门题

2.2522 Problem b

题目描述

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

输入格式

第一行一个整数 $n$，接下来 $n$ 行每行五个整数，分别表示 $a,b,c,d,k$。

输出格式

共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

题目分析

通过莫反可以求出来$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}gcd(i,j)=k$（见p3455），那么考虑容斥，其答案为大集合减去含有一段的再加上含两段的。

代码

//
// Created by mrx on 2022/9/8.
//
#include <bits/stdc++.h>

using ll = long long;


int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif

    std::vector<int> prime, vis(1e6 + 10), mu(1e6 + 10);
    mu[1] = 1;
    for (int i = 2; i <= 1e6; ++i) {
        if (!vis[i]) {
            mu[i] = -1;
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && i * prime[j] <= 1e6; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            } else {
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
    std::vector<int> sum(1e6 + 10, 0);
    for (int i = 1; i <= 1e6; ++i) {
        sum[i] = sum[i - 1] + mu[i];
    }

    int t;
    std::cin >> t;
    while (t--) {
    long long a, b, d;
    std::cin >> a >> b >> d;
    long long ans = 0;
    a /= d, b /= d;
    for (long long l = 1, r; l <= std::min(a, b); l = r + 1) {
        r = std::min(b / (b / l), a / (a / l));
        ans += (a / l) * (b / l) * (sum[r] - sum[l - 1]);

    }
    std::cout << ans << '\n';
    }

    return 0;
}