LUOGU 2257 YY的GCD - 莫比乌斯反演

Description
神犇YY虐完数论后给kAc出了一题:
给定 $N, M,$ 求 $1 \leq x \leq N, 1 \leq y \leq M$ 且 $gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。
kAc不想做，并把这道题扔给了你。
Input Format

Output Format

Sample Input

2
10 10
100 100

Sample Output

30
2971

Constraints
$T = 10^4$
对于 $100$ %的数据， $N,M \leq 10^7$ 。
CCYOS
我的第二道莫比乌斯反演题。
本题即计算 $\sum_{p \in prime}\sum_{i}^{N}\sum_{j}^{M}[gcd(i,j) == p]$
设 $g(p)$ 为 $1 \leq x \leq N, 1 \leq y \leq M$ 且 $gcd(x, y)$ 为 $d$ 的 $(x, y)$ 的个数， $g(k) = \sum_{i}^{N}\sum_{j}^{M}[gcd(i,j) = k]$ 代入原式 $Ans =\sum_{p \in prime}g(p)$ 设 $f(k)$ 为 $1 \leq x \leq N, 1 \leq y \leq M$ 且 $gcd(x, y)$ 为 $k$ 和 $k$ 的倍数的 $(x, y)$ 的个数， $f(k) = \sum_{k|d}g(d) = \lfloor \frac{N}{k} \rfloor · \lfloor \frac{M}{k} \rfloor$ 莫比乌斯反演的第二种形式， $g(k) = \sum_{k|d}\mu(\frac{d}{k})·f(d)$ 代入原式 $Ans = \sum_{p \in prime}\sum_{p|d}\mu(\frac{d}{p})·f(d)$ 令 $a = \frac{d}{p}$ $Ans = \sum_{p \in prime}\sum_{p|d}\mu(a)·f(ap)$ $Ans = \sum_{p \in prime}\sum_{a = 1}^{min(\lfloor \frac{N}{p}\rfloor,\lfloor \frac{M}{p}\rfloor)} \mu(a) \lfloor \frac{N}{ap}\rfloor \lfloor \frac{M}{ap}\rfloor = \sum_{p \in prime} \lfloor \frac{N}{ap}\rfloor \lfloor \frac{M}{ap}\rfloor\sum_{a}\mu(a)$ 再次令 $T = ap,$ $Ans = \sum_{T} \lfloor \frac{N}{T}\rfloor \lfloor \frac{M}{T}\rfloor·(\sum_{p}\mu(\frac{T}{p}))$
code

#include<bits/stdc++.h>
using namespace std;

#define mxn 10000005
int T,N,M,cnt;
int prime[mxn],vis[mxn],done[mxn];
long long sum[mxn],mu[mxn];

inline int read(){
    int ret = 0,fl = 1;
    char c = getchar();
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

inline void get_mu(int n){
    mu[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!vis[i])prime[++cnt] = i,mu[i] = -1;
        for(int j = 1;j <= cnt&&prime[j] * i<= n;++j){
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))break;
            else mu[i * prime[j]] = -mu[i];
        }
    }
    for(int j = 1;j <= cnt;++j) 
        for(int i = 1;i * prime[j] <= n;++i)
            done[i * prime[j]] += mu[i];//储存处理完后的mu[i]
    for(int i = 1;i <= n;++i)
        sum[i] = 1ll * (sum[i - 1] + done[i]);
}

int main(){
    T = read();
    get_mu(10000000);
    for(int i = 1;i <= T;++i){
        N = read();M = read();  
        int limit = min(N,M);
        long long ans = 0;
        for(int l = 1,r;l <= limit;l = r + 1){
                r = min(N/(N/l),M/(M/l));
                ans += 1ll * (N/l) * (M/l) * (sum[r] - sum[l - 1]);//long long
            }
        printf("%lld\n",ans);
    }
    return 0;
}

LUOGU 2257 YY的GCD - 莫比乌斯反演

推荐阅读更多精彩内容