HDU3208(區間指數和)

題意：給兩個數a和b，然後在閉區間[a,b]內的每一個數y都可以表示成x^k=y，要求x盡量最小，k盡量最大，然後求所有的k之和。   分析：對於這個題，我們首先要知道是基於以下的事實來計算的： 對於一個數n，從1~n中假設有x個數是滿足p^k形式的，這裡的k最多到62，那麼對於每一個k，我們需要找到這個數x滿足x^k最 接近n，那麼現在的問題就是對於每一個k找出對應的x，那麼這個怎麼找呢？   我們可以這樣考慮，由於是找最接近的，我們可以先大致確定一個數r，那麼可以通過r=pow(n,1/k)來計算，然後我們分別計 算(r-1)^k,r^k,(r+1)^k，然後看這三個數哪個最接近n就行了，這裡要注意(r+1)^k計算時可能會超過LL，所以有一些處理。 然後就是相當於容斥的部分了。

#include <iostream>  
#include <string.h>  
#include <stdio.h>  
#include <math.h>  
  
using namespace std;  
typedef long long LL;  
  
const LL INF=1e18+300;  
const LL T=(LL)1<<31;  
  
LL num[105];  
  
LL multi(LL a,LL b)  
{  
    LL ans=1;  
    while(b)  
    {  
        if(b&1)  
        {  
            double judge=1.0*INF/ans;  
            if(a>judge) return -1;  
            ans*=a;  
        }  
        b>>=1;  
        if(a>T&&b>0) return -1;  
        a=a*a;  
    }  
    return ans;  
}  
  
LL find(LL x,LL k)  
{  
    LL r=(LL)pow(x,1.0/k);  
    LL t,p;  
    p=multi(r,k);  
    if(p==x) return r;  
    if(p>x||p==-1) r--;  
    else  
    {  
        t=multi(r+1,k);  
        if(t!=-1&&t<=x) r++;  
    }  
    return r;  
}  
  
LL Solve(LL n)  
{  
    int i,k=0;  
    memset(num,0,sizeof(num));  
    if(n<=3) return n;  
    num[1]=n;  
    for(i=2;i<63;i++)  
    {  
        num[i]=find(n,i)-1;  
        if(!num[i]) break;  
    }  
    k=i;  
    for(int i=k-1;i>0;i--)  
        for(int j=1;j<i;j++)  
            if(i%j==0) num[j]-=num[i];  
    LL ans=num[1];  
    for(int i=2;i<k;i++)  
        ans+=(i*num[i]);  
    return ans;  
}  
  
int main()  
{  
    LL n,m;  
    while(cin>>m>>n)  
    {  
        if(m==0&&n==0) break;  
        cout<<Solve(n)-Solve(m-1)<<endl;  
    }  
    return 0;  
}