HDU 2204 容斥原理

佚名 6年前 (2019-04-10) 随笔 1025人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

最后注在开平方时要加一个1e-8的误差，为什么要加，我也不知道，反正网上看到的，最后上代码：

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
long long a[60];
long long ans;
vector <long long> prime;
void init(){
	for(long long i=2;i<60;i++)
	{
		long long j;
		for(j=2;j<i;j++)
		{
			if(i%j==0) break;
		}
		if(j==i) prime.push_back(i);
	}
}
int main()
{
	init();
	long long n;
	while(scanf("%lld",&n)!=EOF)
	{
		memset(a,0,sizeof(a));
		ans=0;
		long long k;
		for(int i=0;true;i++)
		{
			k=(long long)(pow(n,1.0/(prime[i]))+eps);
			if(k<=1) break;
			ans+=(k-1);
			for(int j=i+1;true;j++)
			{
				k=(long long)(pow(n,1.0/(prime[i]*prime[j]))+eps);
				if(k<=1) break;
				ans-=(k-1);
				for(int w=j+1;true;w++)
				{
					k=(long long)(pow(n,1.0/(prime[i]*prime[j]*prime[w]))+eps);
					if(k<=1) break;
					ans+=(k-1);
				}
			}
		}
		ans+=1;
		printf("%lld\n",ans);
	}
}