欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ2818: Gcd(莫比乌斯反演)

程序员文章站 2022-06-03 08:32:36
题意 求$gcd(i, j)$为素数的对数,$ i \leqslant N ,j \leqslant N$ Sol 一开以为要用zap那题的思路暴力求,但是化到一半发现会做了qwq。 设$p_i$为第$i$个素数 我们要求的是 $$ans = \sum_{i = 1}^n \sum_{j = 1}^ ......

题意

求$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;
}
/*

*/