SPOJ4191 POJ3904 Sky Code

10 May 2019 | duanyll | Tags: OI 题解 数论 容斥原理

最近学业繁忙，好久没有搞过OI了。。。

题意

给你n个数，现在让你求出有多少个四元组，满足这四个数的最大公约数等于1,$n \leq 10000$,$a_i \leq 10000$,多组询问，对于每个询问回答多少个四元组满足条件。

分析

用总方案数（$C^{4}_{n}$）减去不合法方案数更容易。于是可以预处理出每一个$a_i$的取值包含多少个不同的质因子数，再看每个取值上有多少个原数组中的取值的因子（考虑每个取值作为四个数GCD的值）。最后统计时要排除有超过两个相同质因子的数，防止重复统计。

容斥原理是奇加偶减，这里因为是用总数减，变成奇减偶加。

代码

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