首页 > ACM题库 > HDU-杭电 > hdu 2204 Eddy’s爱好-数论-[解题报告]C++
2014
01-04

hdu 2204 Eddy’s爱好-数论-[解题报告]C++

Eddy’s爱好

问题描述 :

Ignatius 喜欢收集蝴蝶标本和邮票,但是Eddy的爱好很特别,他对数字比较感兴趣,他曾经一度沉迷于素数,而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的:这些数都能表示成M^K,M和K是正整数且K>1。
正当他再度沉迷的时候,他发现不知道什么时候才能知道这样的数字的数量,因此他又求助于你这位聪明的程序员,请你帮他用程序解决这个问题。
为了简化,问题是这样的:给你一个正整数N,确定在1到N之间有多少个可以表示成M^K(K>1)的数。

输入:

本题有多组测试数据,每组包含一个整数N,1<=N<=1000000000000000000(10^18).

输出:

本题有多组测试数据,每组包含一个整数N,1<=N<=1000000000000000000(10^18).

样例输入:

10
36
1000000000000000000

样例输出:

4
9
1001003332

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents          
by—cxlove

题目:求出1-N里面能表示 成M^K的数有多少个。

容斥解决。首先我们知道因子如果A^B在范围内,那么i^B也在范围之内 (A>i>=1)

另外B考虑质因子,如果A^4在范围内的话,肯定(2*A)^2也在范围内,没有必要重复考虑

指数虽然考虑了质因子,但是我们发现还是有重复,如果说4^3与8^2还是重复了,这是因为他们同为2^6。

我们用Ai表示指数为质因子Pi的数目,那么A1+A2……Ak-(A1交A2)-(A1交A3)……+(A1交A2交A3)……

另外 指数的范围,2^60>10^18所以,指数最大为60,打表60以内的素数,然后容斥

另外2*3*5*7大于60,所以最多只有三个集合的交

网上都说注意精度,貌似没有考虑就水过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define eps 1e-7
using namespace std;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
LL ans,n;
int i;
void dfs(int idx,int num,int k){
    if(k==0){
        LL temp=pow(n,1.0/num);
        if(pow(temp,0.0+num)>n)  temp--;
        temp--;
        if(temp>0)
            ans+=temp*(i&1?1:-1);
        return ;
    }
    if(idx>=17) return;
    if(num*prime[idx]<60)  dfs(idx+1,num*prime[idx],k-1);
    dfs(idx+1,num,k);
}
int main(){
    while(scanf("%I64d",&n)!=EOF){
        ans=0;
        for(i=1;i<=3;i++)
            dfs(0,1,i);
        printf("%I64d\n",ans+1);
    }
    return 0;

}


解题转自:http://blog.csdn.net/acm_cxlove/article/details/7873776


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。