HDU 5212 Code（容斥）
最后更新于：2022-04-01 15:52:51
题意： 输入n个数， 求这n个数的n^2个两两组合的最大公约数x，x(x-1)之和 。
换个思路， 我们如果求出了最大公约数为x的对数cnt， 那么答案就增加x(x-1)cnt^2
那么怎么求以x为最大公约数的对数呢？
我们枚举x的整数倍， 这样就可以知道这些数中是x的整数倍的数有多少个。
那么到底哪些数才是x的最大公约数呢？ 显然， 应该满足：能被x正处而不能被x的倍数整除。
假设能被x整除的数有k1个，能被2x整除的数有k2个， 能被3x整除的数有k3个......
所以gcd() == x 的数就是 k1 - k2 - k3 .......
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 10007;
const int maxn = 10000+5;
int T,n,m;
ll a[maxn],cnt[maxn],d[maxn];
int main() {
while(~scanf("%d",&n)) {
ll maxv = 0;
memset(cnt, 0, sizeof(cnt));
memset(d, 0, sizeof(d));
for(int i=0;i<n;i++) {
scanf("%I64d",&a[i]);
cnt[a[i]]++;
maxv = max(maxv, a[i]);
}
ll ans = 0;
for(int i=2;i<=maxv;i++) {
for(int j=i;j<=maxv;j+=i) {
d[i] += cnt[j];
}
d[i] *= d[i];
}
for(ll i=maxv; i>1; i--) {
for(int j=i*2;j<=maxv;j+=i) {
d[i] -= d[j];
}
ans = (ans+(i*(i-1))*d[i]%mod)%mod;
}
printf("%d\n",ans);
}
return 0;
}
~~~