首页 > 代码库 > Acdream 1114 Number theory 莫比乌斯反演

Acdream 1114 Number theory 莫比乌斯反演

2024-07-17 16:00:57   220人阅读

http://acdream.info/problem?pid=1114

 

题目大意，给你一个序列a，求出这个序列中互质数的有多少对。其中所有的整数的都小于等于222222。

 

f(d) 为 gcd 恰好为 d 的数的对数， F(d) 为 gcd 为 d 的倍数的对数， μ(d) 表示莫比乌斯函数

F(d) = ∑ f(n) 其中（ n % d == 0 ）

莫比乌斯反演一下就可以得到， f(d) = ∑ μ(n / d) * F(n) 其中（ n % d == 0）

所以我们最后所要的答案就是 f(1)， 也就是 ∑ μ(n) * F(n)

下面代码中，cnt[d]是a这个序列中为d的倍数的数字的个数，num[d]是a这个序列中d的个数，所以F[n] = C(cnt[n], 2).

 

#include<cstring>#include<iostream>using namespace std;typedef long long LL;const int INF = 0x7fffffff;const int MAXN = 222222 + 5;LL ans;int n, mx, a[MAXN];int pCnt, vis[MAXN], prime[MAXN];int mu[MAXN], cnt[MAXN], num[MAXN];#define max(a, b) (a) > (b) ? (a) : (b)void mobius(int n){    pCnt = -1, vis[1] = mu[1] = 1;    for(int i = 2; i <= n; ++ i)    {        if(!vis[i])        {            prime[++ pCnt] = i;            mu[i] = -1;        }        for(int j = 0; j <= pCnt && i * prime[j] <= n; ++ j)        {            vis[i * prime[j]] = 1;            if(i % prime[j])                mu[i * prime[j]] = ~mu[i] + 1;            else                mu[i * prime[j]] = 0;        }    }}int main(){    mobius(222222);    cin.sync_with_stdio(false);    while(cin >> n)    {        ans = 0, mx = -INF;        memset(cnt, 0, sizeof(cnt));        memset(num, 0, sizeof(num));        for(int i = 1; i <= n; ++ i)        {            cin >> a[i];            mx = max(mx, a[i]);        }        for(int i = 1; i <= n; ++ i)            ++ num[a[i]];        for(int i = 1; i <= mx; ++ i)            for(int j = i; j <= mx; j += i)                cnt[i] += num[j];        for(int i = 1; i <= mx; ++ i)            ans += (mu[i] * (LL)cnt[i] * (cnt[i] - 1)) >> 1;        cout << ans << endl;    }    return 0;}
View Code

 


联系
我们