POJ 3904 Sky Code - c++编程基础

题意：给出n个数，问找出4个数满足4个数最大公约数为1，最多有多少组。
思路：容斥原理，遍历每个数的素因子，奇数个加偶数个减，然后C(n,4)-sum。

//求得是n个数中，有多少组(a,b,c,d)的公约数为1，值得注意的是这四个数不一定两两互质。
//所以我们从它的反面考虑，先求出公约数不为1的个数。
//思路：把每个数素数分解，记录不重复素因子所能组成的因子，把这些因子的总数统计，并且统计每个因子是由多少个素因子组成
//如这n个数中含2的个数为a,含3的个数为b,含6的个数为c,那么公约数大于1的总数为p=c(a,4)+c(b,4)-c(c,4),总的个数为c(n,4)
//用c(n,4)-p即为所求

AC代码：

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
using namespace std;  
  
typedef __int64 LL;  
const int N=10005;  
const LL II=1000000007;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
LL n,m,pri[N],num[N],co[N],p[N];  
  
void init()  
{  
    memset(p,0,sizeof(p));  
    memset(num,0,sizeof(num));  
    for(LL i=4;i1)  
        pri[numi++]=x;  
    return numi;  
}  
  
void dfs(LL k)  
{  
    LL i,j,t,numi;  
    numi=prime(k);  
    LL sum=0;  
    for(i=1;i<(1<
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef __int64 LL;
const int N=10005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL n,m,pri[N],num[N],co[N],p[N];

void init()
{
    memset(p,0,sizeof(p));
    memset(num,0,sizeof(num));
    for(LL i=4;i1)
        pri[numi++]=x;
    return numi;
}

void dfs(LL k)
{
    LL i,j,t,numi;
    numi=prime(k);
    LL sum=0;
    for(i=1;i<(1<