[来源未知]阶乘和

内存128M,时限1s
阶乘和
【问题描述】
任意一个正整数X都可以表示为n^k，其中n,k为正整数，设f(x)等于满足n^k=x中最大的k。
如f(12) = 1,f(9) = 2,f(64) = 6…..特别的，f(1)不存在。
MM想求出a到b之间（包括a,b）的所有数的f(x)之和。
【输入格式】
两个数a,b(保证a<=b)。
【输出格式】
一个数，即MM所需的答案。
【输入样例】
2 10
【输出样例】
13
【数据范围与约定】
对于40%的数据：a,b<100000;
对于100%的数据：2<=a,b<10^18;

sol:
f[i]能开i次方的数的个数
g[i]最多能开i次方的数的个数
二分一下求f，g[i]=f[i]- ∑kg[i∗k]

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=110000;
ll a,b;
ll ans;
inline int read()
{
char c;
int res,flag=0;
while((c=getchar())>'9'||c<'0') if(c=='-')flag=1;
    res=c-'0';
while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0';
return flag?-res:res;
}
ll f[N];
ll g[N];
ll ksm(ll s,int t,ll x)
{
    ll res=1;
while(t)
    {
if(t&1)
        {
if((double)res*s>x) return x+1;
            res*=s;
        }
if(t!=1&&(double)res*s*s>x) return x+1;
        s*=s;
        t>>=1;
    }
return res;
}
ll solve(ll x)
{
    f[1]=x-1;
    ll l,r,mid,X=sqrt(x);
for(int i=2;i<=60;++i)
    {
        l=1;r=X;
while(l+1<r)
        {
            mid=l+r>>1;
if(ksm(mid,i,x)<=x) l=mid;
else r=mid;
        }
if(ksm(r,i,x)<=x) f[i]=r-1;
else f[i]=l-1;
    }
    ans=0;
for(int i=60;i>=1;--i)
if(f[i]>=0)
    {
        g[i]=f[i];
for(int j=i*2;j<=60;j+=i)
        g[i]-=g[j];
        ans+=g[i]*(ll)i;
    }
return ans;
}
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
cin>>a>>b;
cout<<(solve(b)-solve(a-1));
}