首页 > 代码库 > hdu 2204 Eddy's爱好 容斥原理

hdu 2204 Eddy's爱好 容斥原理

题意:求出1-N里面能表示 成M^K的数有多少个。(N<=10^18)

 1.如果i^B<=N(B>1),那么 (1~i)都能表示成M^K的形式。

2.如果i^4<=N,i^4可以由(i^2)^2来表示所以让指数为素数就能表示出所有了。

3。因为2^60>10^18,  所以只需要列出60以内的素数。

4.若果简单的按照以上对60以内的素数(17个)每次都pow(N,1.0/prime[i])(i<17);

 这样就少考虑重复的情况,像4^3与8^2,指数都是素数他们都是2^6;

所以要利用容斥原理。

5,直接开方会有精度损失 加上eps = 1e-8就行了;

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define ll __int64
const double eps = 1e-8;
ll prim[18]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll n,ans;
void dfs(ll index,ll len,ll s,ll num)
{
    if(num==len)
    {
        ll temp=(pow(n*1.0,1.0/s)+eps)-1;//每次都会重复计算1^s,所以要减去,最后加上一个就行了
        ans+=temp*(len&1?1:-1);
        return ;
    }
    if(index>=17) return ;
    if(s*prim[index]<=60)
        dfs(index+1,len,s*prim[index],num+1);
    dfs(index+1,len,s,num);

}
int main()
{
    while(scanf("%I64d",&n)!=EOF)
    {
        ans=0;
        for(ll i=1;i<=3;i++)
          dfs(0,i,1,0);
        printf("%I64d\n",ans+1);
    }
    return 0;
}









hdu 2204 Eddy's爱好 容斥原理