首页 > 代码库 > Yukari's Birthday

Yukari's Birthday

2024-07-14 20:11:31   228人阅读

hdu4430:http://acm.hdu.edu.cn/showproblem.php?pid=4430

题意：题目的意思就是给你一个s，让你求k,r，其中k,r,满足：k^1+k^2+.....+k^r==s||s-1,并且k*r是最小的，如果有多种情况,r是最小的。

题解：一开始不知道怎么做，听别人说是二分。然后开始往二分上想。

思维过程：一开始就想着怎么二分，首先二分必须找到一个线性关系，找了半天也没有找到什么线性关系，所以不知道怎么二分，也不知道二分什么变量。想了很久，最后看到k*r最小，k是底数，r是指数，所以当r最大时候，k是最小的，同时k*r是最小的，因为k是指数增长的，，当r很大，k只要很小就可以达到s.当k==2的时候，r最多只要40就可以达到s。所以可以枚举r了，然后来找k。这样就慢慢想到，对于固定r，k越大，它的次方和也是随着增大的，所以线性关系出来了，可以二分k，k初始值是s||s-1,所以分两种情况来做，就可以了。不过，这里还要处理一些益处问题，在计算次方和的时候，如果底数大于1e7,其他的值也行，只要不小于1e6就直接跳出，不用计算。具体的，代码中有注释。

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 long long n; 7 long long k,ans1,lastr,lastk,l,mid,r; 8 bool judge(long long s,int num,long long flag){ 9      long long ans=0,temp=s;10      if(s>10000000)return true;//这里是特判，方式爆出long long 因为如果这个数>1e7的话，她的平方必然大于n(考虑n范围)11      for(int i=1;i<=num;i++){12         ans+=temp;13         temp*=s;14         if(ans>=flag)return true;//这里也是防止溢出15      }16   return false;17 }18 bool judge2(long long s,int num){//判断这个数是不是要找的数19      long long ans=0,temp=s;20       if(s>10000000)return false;21      for(int i=1;i<=num;i++){22         ans+=temp;23         temp*=s;24         if(ans>n)return false;25      }26     if(ans==n||ans==n-1)return true;27   return false;28 }29 int main(){30 31     while(~scanf("%I64d",&n)){32            ans1=n-1;lastr=1;lastk=n-1;33       for(int i=2;i<=40;i++){34               l=1,r=n;35            while(l<r){//二分的结果是要么找到了==n的数，要么循环退出36              mid=(l+r)/2;37              if(judge(mid,i,n))38                    r=mid;39              else40                   l=mid+1;41            }42            if(judge2(l,i)&&ans1>i*l){//检查是否是找到==n的那个数43              ans1=i*l;44              lastr=i;45              lastk=l;46            }47              l=1,r=n-1;48            while(l<r){//要么找到==n-1的数，要么退出循环49               mid=(l+r)/2;50               if(judge(mid,i,n-1))51                    r=mid;52               else53                    l=mid+1;54            }55            if(judge2(l,i)&&ans1>i*l){//同上56              ans1=i*l;57              lastr=i;58              lastk=l;59            }60        }61        printf("%I64d %I64d\n",lastr,lastk);62     }63 }
View Code

 


联系
我们