发布于  更新于 

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;
}
}