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.
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.
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 0Hint9 = 1^2 + 2^2 + 1 * 2 * 2 53 = 2^3 + 3^3 + 2 * 3 * 3
Source
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;
}