[原创]hdu 2204 Eddy's爱好 [容斥原理]【组合数学】
[原创]hdu 2204 Eddy’s爱好 [容斥原理]【组合数学】
2017-02-11 14:04:07 Tabris_ 阅读数:366
博客爬取于2020-06-14 22:41:39
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54982748
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2204
------------------------------------------------------------------------------------------------------------------.
2017 口碑商家客流量预测大赛》
Eddy’s爱好
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2436 Accepted Submission(s): 1118
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
Recommend
lcy
------------------------------------------------------------------------------------------------------------------.
题目大意:
求在[1,n]中能用表示的数的个数,
解题思路:
,所以K一定小于60,
又因为 ,所以只要求指数为质数的就行了,
,即x的就是指数为p的个数
利用容斥原理,去掉重复的就行了,
于2^60>10^18,235*7>60,所以只要枚举到三即可。
注:最后一个样例应该有问题, 我的代码和网上代码结果都是1001003331,找了好久的精度…
附本题代码
------------------------------------------------------------------------------------------------------------------.
1 | LL n,ans; |