首页 > 代码库 > poj 3904 Sky Code

poj 3904 Sky Code

2024-08-06 22:03:43   219人阅读

点击打开链接

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进制查找素因子组合

 124
1T  
2 T 
3TT 
4  T
5T T
6 TT
7TTT

#include<iostream>
#include<stdio.h>
#include<string.h>
#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<<tol);i++){  //总共有1~2^tol-1个组合
        k=1,sum=0;
        for(j=0;j<tol;j++)//巧妙利用二进制来查找到所有素因子组合构成的数
            if(i&(1<<j)){
                k*=prime[j];
                sum++;
            }
        cnt[k]++; //记录含有因子K的数的个数,比如n=30,则cnt[2]++,cnt[3]++,cnt[5]++;
                                            //cnt[6]++,cnt[10]++,cnt[15]++;cnt[30]++;
        num[k]=sum;//记录k中含有素因子的个数 num[2]=1,num[3]=1,num[5]=1,num[6]=2,
    }                                       //num[10]=2,num[15]=2,num[30]=3,
}
int main(){
   int m,n;
   long long i;
   for(i=4;i<MAX;i++)        //先打表，提高效率，i<4时p[i]为0；
        p[i]=i*(i-1)*(i-2)*(i-3)/24;
   while(~scanf("%d",&n)){
       memset(cnt,0,sizeof(cnt));
       for(i=0;i<n;i++){
           scanf("%d",&m);
           Solve(m);        //求解其素因子，并统计相关数据
       }
       long long ans=0;
       for(i=0;i<MAX;i++)
           if(cnt[i]>=4)//剪枝，必须大于等于四
               if(num[i]&1) //假如含有素因子个数为奇数，则加上；否则减去
                    ans+=p[cnt[i]];
               else
                    ans-=p[cnt[i]];
       cout<<p[n]-ans<<endl; //最后用总的减去不符合的四元组个数
   }return 0;
}

poj 3904 Sky Code


联系
我们