题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=71738
题意：给你一个整数序列a1, a2, a3, ... , an。求gcd(ai, aj) = 1 且 i < j的对数。
思路：利用莫比乌斯反演很快就能得到公式，但是求解时我们要知道序列中1, 2, 3, ... , max(a1, a2, ... , an)的倍数各是多少。我们用num[i]=k，来表示序列中有k个数是i的倍数，那么这部分对结果的影响是mu[i]*(k - 1) * k / 2。最后的结果就是sigma(mu[i]*(k - 1) * k / 2)。
code：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = ;
int num[MAXN]; // num[i]表示 满足(i|ak)的个数
int tmp[MAXN]; // 标记哪些数有
bool check[MAXN];
int primes[MAXN];
int mu[MAXN]; void moblus()
{
memset(check, false, sizeof(check));
mu[] = ;
int cnt = ;
for (int i = ; i < MAXN; ++i) {
if (!check[i]) {
primes[cnt++] = i;
mu[i] = -;
}
for (int j = ; j < cnt; ++j) {
if (i * primes[j] > MAXN) break;
check[i * primes[j]] = true;
if (i % primes[j] == ) {
mu[i * primes[j]] = ;
break;
} else {
mu[i * primes[j]] = -mu[i];
}
}
}
} int main()
{
moblus();
int n;
while (scanf("%d", &n) != EOF) {
memset(num, , sizeof(num));
memset(tmp, , sizeof(tmp));
int tmax = ;
for (int i = ; i < n; ++i) {
int x;
scanf("%d", &x);
++tmp[x];
tmax = max(tmax, x);
}
for (int i = ; i <= tmax; ++i) {
for (int j = i; j <= tmax; j += i) {
num[i] += tmp[j];
}
}
LL ans = ;
for (int i = ; i <= tmax; ++i) {
ans += (LL)mu[i] * num[i] * (num[i] - ) / ;
}
printf("%lld\n", ans);
}
return ;
}