HDU Integer's Power（容斥原理）

题意

求[l,r]的最大指数和（1<=l,r<=10^18）

最大指数和（如64=8^2=4^3=2^6,所以64的最大指数和是6）

题解

很明显我们可以先求出[1,n]的最大指数和，然后再作差。

我们可以先求出num[i]代表[1,n]中最大指数为i的数有多少个。

然后枚举全部的i，然后让答案加上i*num[i]；

那么怎么求num[i]呢

我们可以求出[1,n]中指数为x的数有多少个作为num[x]的初步值。这个用n^1/x就可以求出（不过要注意精度问题，及其恶心，看代码吧）

然后这个num却对是不对的。我们发现16=4^2=2^4,num[2]中却有16，所以我们用num[2]-num[4]就行了。

我们发现对于每一对i>j且i%j==0num[j]都需要减num[i]，不过我们要倒序枚举j。

具体看代码吧。

 #include<iostream>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const long long INF=1e18+;

 const long long inf=(long long)<<;

 long long dp[],a,b,n;

 long long ksm(long long x,long long b){

     long long tmp=;

     while(b){

         if(b&){

             double num=1.0*INF/tmp;

             if(x>num)return -;

             tmp=tmp*x;

         }

         b>>=;

         if(x>inf&&b>)return -;

         x=x*x;

     }

     return tmp;

 }

 long long calc(long long n,long long x){

     long long a=(long long)(pow((double)(n),1.0/x)+1e-);

     long long b=ksm(a,x);

     if(b==n)return a;

     if(b==-||b>n)return a-;

     long long c=ksm(a+,x);

     if(c!=-&&c<=n)return a+;

     else return a;

 }

 long long solve(long long x){

     if(x==)return ;

     if(x==)return ;

     long long k;

     dp[]=x;

     for(long long i=;i<=;i++){

         dp[i]=calc(x,i)-;

         if(dp[i]==){

             k=i-;

             break;

         }

     }

     for(long long i=k;i>=;i--)

         for(long long j=;j<i;j++){

             if(i%j==)dp[j]-=dp[i];

         }

     long long ans=dp[];

     for(long long i=;i<=k;i++){

         ans+=dp[i]*i;

     }

     return ans;

 }

 int main(){

     while(scanf("%lld%lld",&a,&b)!=EOF){

         if(a==&&b==)break;

         printf("%lld\n",solve(b)-solve(a-));

     }

     return ;

 }

巴特西

HDU Integer's Power（容斥原理）

题意

题解

最新文章

热门文章