Luogu P2257 YY的GCD

题目描述

https://www.luogu.com.cn/problem/P2257

简要题意：求 $\sum_{p}\sum_{i=1}^n\sum_{j=1}^m[(i,j)=p]$

$T=10^4,n,m\le 10^7$

Solution

$$\begin{aligned} ans&=\sum_{p}\sum_{i=1}^n\sum_{j=1}^m[(i,j)=p]\\ &=\sum_{p}\sum_{i=1}^n\sum_{j=1}^m[(\frac{i}{p},\frac{j}{p})=1]\\ &=\sum_{p}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[(i,j)=1]\\ &=\sum_{p}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|(i,j)}\mu(d)\\ &=\sum_{p}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\sum_{d|i}\sum_{d|j}1\\ &=\sum_{p}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor\\ &=\sum_{T=1}^n\sum_{p|T}\mu(\frac{T}{p})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{p|T}\mu(\frac{T}{p})\\ \end{aligned}$$

我们令 $f(T)=\sum_{p|T}\mu(\frac{T}{p})$，这个东西可以 $O(n)$ 预处理

#include <iostream>
#include <cstdio>
#define maxn 10000010
#define ll long long
using namespace std;

int n, m, k; 

int pri[maxn], cnt, mu[maxn], f[maxn]; bool isp[maxn]; 
void init_isp(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
            mu[i * pri[j]] = -mu[i]; 
        }
    }
    for (int i = 1; i <= cnt; ++i)
        for (int j = pri[i], k = 1; j <= n; j += pri[i], ++k) f[j] += mu[k];
    for (int i = 1; i <= n; ++i) f[i] += f[i - 1]; 
}

void work() {
    cin >> n >> m; if (n > m) swap(n, m); ll ans = 0; 
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (ll) (f[r] - f[l - 1]) * (n / l) * (m / l); 
    }
    cout << ans << "\n"; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; init_isp(10000000); 
    while (T--) work(); 
    return 0;
}