-数论-莫比乌斯反演-容斥- [SP26017]GCDMAT - GCD OF MATRIX

题目描述

Link

Solution

其实如果这道题没有容斥的操作就是这样：

$$\sum_{i = 1}^n \sum_{j = 1}^m \gcd(i, j)$$

然后我们可以推一下：

$$\sum_{i = 1}^n \sum_{j = 1}^m \gcd(i, j)​$$ $$\sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) == d]$$ $$\sum_{d = 1}^n \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i ,j) == 1] ​$$ $$\sum_{d = 1}^n \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{d | \gcd(i, j)} \mu(d)​$$ $$\sum_{d = 1}^n \sum_{a = 1}^n \mu(a) {\lfloor \frac{n}{ad} \rfloor}{\lfloor \frac{m}{ad} \rfloor}​$$

设 $T=ad​$

$$\sum_{T = 1}^n {\lfloor \frac{n}{T} \rfloor}{\lfloor \frac{m}{T} \rfloor} \sum_{d | T} d \mu({\lfloor \frac{T}{d} \rfloor})​$$

因为 $\sum_{d | T} d \mu({\lfloor \frac{T}{d} \rfloor})​$ 这部分是狄利克雷卷积的形式，而 $id * \mu = \varphi​$

所以线性筛一遍欧拉函数再用整除分块就行了。

最后再用容斥瞎搞搞就可以了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 500010
#define MOD 1000000007
#define ll long long
#define int long long
int p[MAXN + 10], tot, phi[MAXN + 10], T, g[MAXN + 10], answ;
bool chk[MAXN + 10];
template <typename Tp>
Tp min(Tp a, Tp b) {
    if (a < b) return a;
    else return b;
}
template <typename Tp>
Tp max(Tp a, Tp b) {
    if (a > b) return a;
    else return b;
}
void sieve() {
    phi[1] = 1;
    chk[1] = true;
    for (int i = 2; i <= MAXN; i++) {
        if (!chk[i]) {
            p[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * p[j] <= MAXN; j++) {
            chk[i * p[j]] = 1;
            if (!(i % p[j])) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
    for (int i = 1; i <= MAXN; i++) {
        g[i] = (g[i - 1] + phi[i]) % MOD;
    }
}
int sum(int x, int y) {
    int n = min(x, y);
    int m = max(x, y);
    ll ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (((n / l) % MOD * (m / l) % MOD) % MOD) * ((g[r] - g[l - 1] + MOD) % MOD) % MOD;
    }
    return (ans % MOD);
}
int a, b, c, d, n, m;
signed main() {
    sieve();
    scanf("%lld", &T);
    scanf("%lld%lld", &n, &m);
    while (T--) {
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        answ = (sum(c, d) + sum(a - 1, b - 1) - sum(c, b - 1) - sum(d, a - 1) + 2 * MOD) % MOD;
        printf("%lld\n", answ % MOD);
    }
}