POJ 3904 Sky Code 容斥原理

POJ 3904

題意 :  求給定的n個數中4個數的最大公約數為1的組合數

剛開始看居然隻有300不到的人A了，就認為可能不簡單，原來做起來的話隻是比較清楚的容斥原理。

首先要求出每一個數的素因子，然後對于求出的素因子進行組合，加到vis[i][j]上，表示由i個素因子組合成的數j的個數。

然後就是容斥原理，總的組合數為sum = n*(n-1)*(n-2)*(n-3)/24  于是ans = sum - 由一個素因子組合成的四個數的組合數 

+ 由兩個素因子組合成的四個數的組合數 - 。。。     有了思路就快速敲出代碼了，調試了下沒什麼問題于是就直接交了，居然AC了~~~

1A的感覺還是挺不錯的~~~

#include <stdio.h>
#include <string.h>
#define LL __int64
const int maxn = 11111;
int vis[22][maxn], cur[22] , d[22];
int top ;
void get(int now,int num,int tot)
{
	int i;
	if(num == tot)
	{
		int sum = 1;
		for(i = 0;i < tot; i++)
			sum *= d[i];
		vis[tot][sum]++;
	}
	else
		for(i = now;i < top; i++)
		{
			d[num] = cur[i];
			get(i+1,num+1,tot);
		}
}

int main()
{
	LL n;
	int i,j,k,x;
	while(scanf("%I64d", &n)!=-1)
	{
		memset(vis,0,sizeof(vis));
		for(i = 0;i < n; i++)
		{
			memset(cur,0,sizeof(cur));
			int num = 0;
			scanf("%d", &x);
			for(j = 2;j*j <= x; j++)
			{
				if(x%j == 0)
				{
					while(x%j == 0)
						x /= j;
					cur[num++] = j;
				}
			}
			if(x != 1)
				cur[num++] = x;
			top = num;
			for(j = 0;j < num;j ++)
				get(0,0,j+1);
		}
		LL ans = n*(n-1)*(n-2)*(n-3)/24;
		for(i = 1;i <= 20; i++)
		{
			for(j = 2;j <= 10000; j++)
			{
				if(vis[i][j]>=4)
				{
					LL change = 1;
					for(k = vis[i][j];k > vis[i][j]-4; k--)
						change = change*k;
					change = change/24;
					if(i&1)
						ans -= change;
					else
						ans += change;
				}
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}