SPOJ4191 POJ3904 Sky Code
容斥原理
数论
题解
oi
最近学业繁忙，好久没有搞过OI了。。。
题意
给你n个数，现在让你求出有多少个四元组，满足这四个数的最大公约数等于1,,,多组询问，对于每个询问回答多少个四元组满足条件。
分析
用总方案数（）减去不合法方案数更容易。于是可以预处理出每一个的取值包含多少个不同的质因子数，再看每个取值上有多少个原数组中的取值的因子（考虑每个取值作为四个数GCD的值）。最后统计时要排除有超过两个相同质因子的数，防止重复统计。
容斥原理是奇加偶减，这里因为是用总数减，变成奇减偶加。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
const int MAXN = 10010;
const int AMXA = 10000;
int64 C4(int64 n){
return n*(n-1)*(n-2)*(n-3) / 24;
}
int prime[MAXN];
bool isntp[MAXN];
int pcnt;
int pfac_cnt[MAXN];
void count_factor(){
for(int i = 2;i<=AMXA;i++){
if(!isntp[i]){
prime[pcnt++] = i;
pfac_cnt[i] = 1;
for(int j = i*2;j<=AMXA;j+=i){
isntp[j] = true;
if(j % (i*i) != 0 && pfac_cnt[j] != -1){
pfac_cnt[j]++;
}else{
pfac_cnt[j] = -1;
}
}
}
}
}
int a[MAXN];
int vcnt[MAXN];
int all_fac[MAXN];
int main(){
int n;
count_factor();
while(cin >> n){
memset(vcnt,0,sizeof vcnt);
memset(all_fac,0,sizeof all_fac);
for(int i = 1;i<=n;i++){
cin >> a[i];
vcnt[a[i]]++;
}
for(int i = 2;i<=AMXA;i++){
for(int j = i;j<=AMXA;j+=i){
all_fac[i] += vcnt[j];
}
}
int64 ans = C4(n);
for(int i = 2;i<=AMXA;i++){
if(pfac_cnt[i] > 0){
if(pfac_cnt[i] & 1){
ans -= C4(all_fac[i]);
}else{
ans += C4(all_fac[i]);
}
}
}
cout << ans << endl;
}
}
|
