poj 3904 Sky Code

poj 3904 Sky Code

 

Sky Code Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 1562   Accepted: 478

 

Description

Stancu likes space travels but he is a poor software developer and will never be able to buy his own spacecraft. That is why he is preparing to steal the spacecraft of Petru. There is only one problem – Petru has locked the spacecraft with a sophisticated cryptosystem based on the ID numbers of the stars from the Milky Way Galaxy. For breaking the system Stancu has to check each subset of four stars such that the only common divisor of their numbers is 1. Nasty, isn’t it? Fortunately, Stancu has succeeded to limit the number of the interesting stars to N but, any way, the possible subsets of four stars can be too many. Help him to find their number and to decide if there is a chance to break the system.

Input

In the input file several test cases are given. For each test case on the first line the number N of interesting stars is given (1 ≤ N ≤ 10000). The second line of the test case contains the list of ID numbers of the interesting stars, separated by spaces. Each ID is a positive integer which is no greater than 10000. The input data terminate with the end of file.

Output

For each test case the program should print one line with the number of subsets with the asked property.

Sample Input

4
2 3 4 5 
4
2 4 6 8 
7
2 3 4 5 7 6 8

Sample Output

1 
0 
34

題目翻譯：給出n(n<10000)個數，這些數<=10000，要求選出四個數字且他們的最大公約數為1的（注意：不需要兩兩互質），有多少種選法。

解題思路：本題可以先計算n個數字選四個總共有多少種選法，然後減去公約數不是1的。把共同具有某一素因子的數字劃分到同一個集合，屬於統一集合的四個數最大公約數一定大於1，如果四個數字不同時屬於任何集合則最大公約數一定為1。用總的組合數減去那些四個數字同時被同一個集合包括了的組合數，所得結果即為最終答案。但是這些一個四個數字的組合可能同時屬於若干個集合，因此需要在這些集合之間進行容斥原理，以求每個需要被減去的四個數字的組合都恰好被減掉一次。

首先，先將算法流程說一下，原理後面會有
Step 1：預處理，求組合數C（n，4），存於數組p中，方便下面運算！
Step 2：組合素數，用prime數組記錄由m(m<=5)個素數相乘所得數的素因子
Step 3：讀入當前數為a，將a分解為質因數形式，注意每個質因數只被記錄一次
例如： 182=2*7*13 ———> m=3 so，相加
2=2 ——>m=1 so，相加
91=7*13 ——>m=2 so，相減
注意12=2^2*3等這種是B=p1^k1*p2^k2+...這種有質因數指數不為一的合數記錄不同因子的個數
12=2*2*3 則 12會被分為2*3，多余的2被消去了，因此m=2；
Step 4：將分出的素數進行組合，並統計每種的方案數
例如：12=2^2*3——>12=2*3——>cnt[2]++,cnt[3]++,cnt[6]++
Step 5：處理之後，ans賦值為0
Step 6：for i 2-->10000
if （m==奇數） ans:=ans+C(cnt[i],4)
else ans:=and-C(cnt[i],4);
Step 7：輸出ans
原理：首先考慮一個問題，1000以內6,7,8,9的倍數有多少個？答案是
1000div6+1000div7+1000div8+1000div9
-1000div(6*7)-1000div(6*8)-1000div(6*9)-1000div(7*8)-1000div(7*9)-1000div(8*9)
+1000div(6*7*8)+1000div(6*8*9)+1000div(7*8*9)
-1000div(6*7*8*9)
這是容斥原理的一個最簡單的應用，類比這道題，Step3到4其實將每個數a的不重復約數記錄了下來，
有公共約數的四個數的方案要從ans中減去，多減的要加上
顯然m為奇時要減，m為偶時要加，這和”1000以內6,7,8,9的倍數有多少個？“這個問題奇偶是反的，
由於a最大為10000，所以m最大可以有5 (2*3*5*7*11<10000,2*3*5*7*11*13>10000)
此表格解釋利用2進制查找素因子組合

 

  1 2 4 1 T     2   T   3 T T   4     T 5 T   T 6   T T 7 T T T

 

 

#include
#include
#include
#define MAX 10005
using namespace std;
int cnt[MAX],num[MAX],prime[5];//數組不必過大，5個單位即可
long long  p[MAX]={0}; //必須用大整數
void Solve(int  n){
    int i,j,tol=0,k,sum;
    for(i=2;i*i<=n;i++){ //計算素因子個數
        if(n%i==0)
            prime[tol++]=i;
        while(n%i==0)//去重復因子
            n/=i;
    }
    if(n!=1) prime[tol++]=n;    //如果本身就是大於n開方的素數，需要加一，這點不要忘記
    for(i=1;i<(1<=4)//剪枝，必須大於等於四
               if(num[i]&1) //假如含有素因子個數為奇數，則加上；否則減去
                    ans+=p[cnt[i]];
               else
                    ans-=p[cnt[i]];
       cout<