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;
#define max(a, b) (a) > (b) ? (a) : (b)
LL ans;
int n, mx, a[MAXN];
int cnt[MAXN], num[MAXN];
int pCnt, vis[MAXN], prime[MAXN], mu[MAXN];
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; ++ j)
{
if(i * prime[j] > n)
break;
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = ~mu[i] + 1;
}
}
}
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
转载于:https://www.cnblogs.com/tank39/p/3913415.html