[原创]hdu 2204 Eddy's爱好 [容斥原理]【组合数学】

Tabris

CSDNhdu组合数学

发布于：2017年2月11日

次浏览

[原创]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]中能用M^K表示的数的个数，

解题思路：

N \in [1,10^{8}]，所以 K 一定小于 60,
又因为 x^{a*b} = x^{a^b} ，所以只要求指数为质数的就行了，

x^p<=n，即 x 的就是指数为 p 的个数

利用容斥原理，去掉重复的就行了，

于 2^60>10^18，235*7>60，所以只要枚举到三即可。

注：最后一个样例应该有问题， 我的代码和网上代码结果都是 1001003331，找了好久的精度....

附本题代码
------------------------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

LL n,ans;

int prime[100]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};

void dfs(int id,bool flag,int val,int cnt){
    if(cnt == 0){
        LL tmp = pow(n,1.0/val); //指数为val的个数
        if(pow(tmp,0.0+val)>n) tmp--;tmp--;
        if(tmp>0){
            if(flag) ans+=tmp;
            else     ans-=tmp;
        }
        return ;
    }
    if(id>=17) return ;
    if(val*prime[id]<60)    dfs(id+1,flag,val*prime[id],cnt-1);
    dfs(id+1,flag,val,cnt);
}

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

本页文档最后更新于：2021年5月16日

CSDN