P3455 ZAP-Queries

莫反入门题

1.3455 ZAP-Queries

题目描述

密码学家正在尝试破解一种叫 BSA 的密码。

他发现，在破解一条消息的同时，他还需要回答这样一种问题：

给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 元组 $(x,y)$ 的数量。

因为要解决的问题实在太多了，他便过来寻求你的帮助。

题目分析

题目即求$\sum\limits^a_{i=1}\sum \limits_{j=1}^bgcd(i,j)=d$

考虑莫比乌斯反演，$[gcd(i,j)=1]=\sum\limits_{ gcd(i,j)\mid d}\mu (d)$那么题目所求值可以变为$\sum\limits_{i=1}^{a/d}\sum\limits_{j=1}^{b/d}\sum\limits_{gcd(i,j)\mid k}\mu (k)$，那么把k提取到前面，得到：$\sum\limits_{k=1}^{\frac{a}{d}}\sum\limits_{i=1}^{\frac{a}{d}}\sum\limits_{j=1}^{\frac {b}{d}}[k\mid gcd(i,j)]*\mu (k)$提取出$\sum\limits_{k=1}^{\frac{a}{d}}\mu (k)\sum\limits_{i=1}^{\frac{a}{d}}\sum\limits_{j=1}^{\frac {b}{d}}[k\mid gcd(i,j)]$,根据gcd的性质，只有当$i,j都是k的倍数的时候[k\mid gcd(i,j)]=1$,那么上式变为$\sum\limits_{k=1}^{\frac{a}{d}}\mu (k)\sum\limits_{i=1}^{\frac{a}{kd}}\sum\limits_{j=1}^{\frac {b}{kd}}1=\sum\limits_{k=1}^{\frac{a}{d}}\mu (k)\frac{a}{kd}\frac {b}{kd}$要球这个式子，就可以进行整除分块。

代码

//
// 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;
}