hdu 2204 Eddy's爱好 容斥原理

时间:2021-07-26 01:05:48

Eddy's爱好

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description
Ignatius 喜欢收集蝴蝶标本和邮票,但是Eddy的爱好很特别,他对数字比较感兴趣,他曾经一度沉迷于素数,而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的:这些数都能表示成M^K,M和K是正整数且K>1。
正当他再度沉迷的时候,他发现不知道什么时候才能知道这样的数字的数量,因此他又求助于你这位聪明的程序员,请你帮他用程序解决这个问题。
为了简化,问题是这样的:给你一个正整数N,确定在1到N之间有多少个可以表示成M^K(K>1)的数。
 
Input
本题有多组测试数据,每组包含一个整数N,1<=N<=1000000000000000000(10^18).
 
Output
对于每组输入,请输出在在1到N之间形式如M^K的数的总数。
每组输出占一行。
 
Sample Input
10
36
1000000000000000000
 
Sample Output
4
9
1001003332
 
Author
Eddy
思路:根据指数找个数,由于n^6=(n^2)^3=(n^3)^2;容斥解决
   比如:10以内的二次方;sqrt(10)=3个;注意精度。。。
   涨知识:求根号,pow(n,1.0/m);
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 999999999
#define pi 4*atan(1)
//#pragma comment(linker, "/STACK:102400000,102400000")
ll p[]={,,,,,,,,,,,,,,,,},ans;
ll gcd(ll x,ll y)
{
return y==?x:gcd(y,x%y);
}
void dfs(ll lcm,ll pos,ll step,ll x)
{
if(lcm>)
return;
if(pos==)
{
if(step==)
return;
ll temp=(ll)pow(x,1.0/lcm+1e-);
if(step&)
ans+=temp-;
else
ans-=temp-;
return;
}
dfs(lcm,pos+,step,x);
dfs(lcm/gcd(p[pos],lcm)*p[pos],pos+,step+,x);
}
int main()
{
ll x,y,z,i,t;
while(~scanf("%I64d",&x))
{
ans=;
dfs(,,,x);
printf("%I64d\n",ans+);
}
return ;
}