首页 > > 程序设计 > C/C++ >

BZOJ2818: Gcd(莫比乌斯反演)

2018-07-20 05:47:48来源：博客园阅读 ()

题意

求$gcd(i, j)$为素数的对数，$ i \leqslant N ,j \leqslant N$

Sol

一开以为要用zap那题的思路暴力求，但是化到一半发现会做了qwq。

设$p_i$为第$i$个素数

我们要求的是

$$ans = \sum_{i = 1}^n \sum_{j = 1}^n [gcd(i, j) = p_i]$$

$$ = \sum_{i = 1}^{\frac{n}{p_i}} \sum_{j = 1}^{\frac{n}{p_i}} [gcd(i, j) = 1]$$

根据定理

$$\sum_{i = 1}^n \sum_{j = 1}^n [gcd(i, j) = 1] = 2\phi(i) - 1$$

而且$10^7$以内的质数只有大约$6 * 10^5$个

直接对$\phi$做前缀和然后暴力算就行了

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL long long 
#define rg register 
//#define int long long 
using namespace std;
const int MAXN = 1e7 + 10, mod = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int prime[MAXN], vis[MAXN], tot;
LL phi[MAXN];
void GetPhi(int N) {
    vis[1] = phi[1] = 1;
    for(rg int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
        for(rg int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) {phi[i * prime[j]] = phi[i] * prime[j]; break;}
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for(rg int i = 2; i <= N; i++) phi[i] += phi[i - 1];
}
inline LL F(int N) {
    return (phi[N] << 1) - 1;
}
int main() {
    GetPhi(1e7 + 5);
    int N = read();
    LL ans = 0;
    for(rg int i = 1; i <= tot && prime[i] <= N; i++) 
        ans += F(N / prime[i]);
    printf("%lld\n", ans);
    return 0;
}
/*

*/