容斥原理po3904j
- 格式：docx
- 大小：14.48 KB
- 文档页数：3
题意：给出一个数列，让求出数量为4的子集，并且这四个数的最大公约数为1 的个数。
数列的个数为10000，并且元素的最大值为10000
思路：如果暴利枚举的话，肯定要超时。最开始的时候我发现了用容斥原理可以做，但是我
进行容斥原理的时候是用的搜索，就超时了。后来才发现有一个很神奇的方法。
这道题我首先学会了求数的因子的一个简单的方法，不用开始打出素数表。
其实只需要从2 往后枚举到i*i==n的时候。当枚举到一个数时可以整除的话，那么我就
把这个数当成因子，然后把这个数多次除以i，直至没有i因子为止。直至结束。最后如果
剩余的数不为1，那么这个数也是一个数因子。
Ans = C（n,4）-sum（C（a1j，4））+sum（C(a2j,4)）…….
aij表示 该数是由4个数因子组成，并且是这种情况的第j个的数目。
但是如何求呢，开始我用的是搜索，果断不行，因为10000以内的素数有1000多个，搜索
的话果断超时，最后在网上看到一个做法，很神奇，利用到了位运算
具体是这样的，我们找出一个数的因子，（不超过6个），然后用位运算来枚举当前的数因子
可以组成的数。具体是这样子的
for(int i = 1; i <(1<
sum = 0; now = 1;
for(int j = 0 ; j < cnt;j++)
{
if(i&(1<
sum ++;
now *= p[j];
}
}
count[now]++;
num[now] = sum;
}
最后直接用容斥原理解决就行了
AC代码：
#include
#include
#include
using namespace std;
const int N = 10100;
int count[N],num[N],n;
__int64 C[N];
void get_C()
{
for(__int64 i = 4; i
}
void get_count(int n)
{
int p[N],sum,cnt = 0,x = n,now;
for(int i = 2; i*i<=n;i++)
{
if( n%i == 0)
{
p[cnt++] = i;
while(n%i == 0)
n /= i;
}
}
if(n != 1)
p[cnt++] = n;
for(int i = 1; i <(1<
sum = 0; now = 1;
for(int j = 0 ; j < cnt;j++)
{
if(i&(1<
sum ++;
now *= p[j];
}
}
count[now]++;
num[now] = sum;
}
}
void init()
{
int a;
memset(count,0,sizeof(count));
memset(num,0,sizeof(num));
for(int i = 0;i < n; i++)
{
scanf("%d",&a);
get_count(a);
}
}
int main()
{
__int64 ans;
get_C();
while(scanf("%d",&n)!=EOF)
{
init();
ans = C[n];
for(int i = 2;i <= N ;i++)
{
if(num[i]%2)
ans -= C[count[i]];
else ans += C[count[i]];
}
printf("%I64d\n",ans);
}
return 0;
}
