好贷网好贷款

hdu4282(单调性+二分)

发布时间:2016-12-5 4:35:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu4282(单调性+二分)",主要涉及到hdu4282(单调性+二分)方面的内容,对于hdu4282(单调性+二分)感兴趣的同学可以参考一下。

A very hard mathematic problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3103    Accepted Submission(s): 896 Problem Description   Haoren is very good at solving mathematic problems. Today he is working a problem like this:   Find three positive integers X, Y and Z (X < Y, Z > 1) that holds    X^Z + Y^Z + XYZ = K   where K is another given integer.   Here the operator “^” means power, e.g., 2^3 = 2 * 2 * 2.   Finding a solution is quite easy to Haoren. Now he wants to challenge more: What’s the total number of different solutions?   Surprisingly, he is unable to solve this one. It seems that it’s really a very hard mathematic problem.   Now, it’s your turn.   Input   There are multiple test cases.   For each case, there is only one integer K (0 < K < 2^31) in a line.   K = 0 implies the end of input.      Output   Output the total number of solutions in a line for each test case.   Sample Input 9 53 6 0   Sample Output 1 1 0    Hint 9 = 1^2 + 2^2 + 1 * 2 * 2 53 = 2^3 + 3^3 + 2 * 3 * 3   Source 2012 ACM/ICPC Asia Regional Tianjin Online   Recommend liuyiding           本题给定K,要求满足条件的X,Y,Z使得X^Z+Y^Z+X*Y*Z=K,其中0<X<Y,Z>1。开始时我单从数学角度寻求优化,但没有发现任何有效的策略。于是转用枚举法,可以枚举其中两个的值,然后依据单调性二分求解。枚举时应选择Z和X,Y中的一个,然后二分求解第三个。我枚举的是X,Z,然后利用单调性二分求解Y。此时有了另一个优化策略,我们可以预处理X^Z次幂,此过程中可以利用累乘而避免数学库函数pow的调用。总的时间复杂度为O(N*log(N))。 #include<iostream> #include<cmath> #include<cstdio> #include<cstring> using namespace std; const __int64 MAXN=(1<<16)+10; const __int64 INF=2147483648;//1<<31; __int64 Reselt[MAXN][32]; __int64 k; void init() { __int64 i,j; memset(Reselt,-1,sizeof(Reselt)); for(i=1;i<MAXN-5;i++) { Reselt[i][1]=i; for(j=2;j<=31;j++) { Reselt[i][j]=Reselt[i][j-1]*i; if(Reselt[i][j]>=INF) { Reselt[i][j]=-1; break; } } } } bool Bin_research(__int64 l,__int64 Exp,__int64 sum) { __int64 i,low=l+1,high=MAXN,mid; while(low<=high) { mid=(low+high)>>1; if(-1==Reselt[mid][Exp]){high=mid-1;continue;} if(Reselt[mid][Exp]+l*mid*Exp==sum) { return true; } if(Reselt[mid][Exp]+l*mid*Exp<sum)low=mid+1; else high=mid-1; } return false; } void Solve() { __int64 i,j,sum,ans=0; for(i=1;i<MAXN-5;i++) { for(j=2;j<=31;j++) { if(-1==Reselt[i][j])break; sum=k-Reselt[i][j]; if(sum<=0)break; if(Bin_research(i,j,sum)) ans++; } } printf("%I64d\n",ans); } int main() { // freopen("in.txt","r",stdin); init(); while(~scanf("%I64d",&k),k) { Solve(); } return 0; }    

上一篇:编程一次遍历搜索到中间节点,如果节点数为偶数,取中间两节点中前一节点
下一篇:使用cURL操作Swift

相关文章

相关评论