首页 > 代码库 > hdu 4282 A very hard mathematic problem(二分)

hdu 4282 A very hard mathematic problem(二分)

2024-07-14 14:49:06   221人阅读

A very hard mathematic problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3990    Accepted Submission(s): 1170


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
 

题解及代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;

LL quick_mod(LL a,LL b)
{
    LL t=1;
    while(b)
    {
        if(b&1) t*=a;
        b/=2;
        a*=a;
    }
    return t;
}

int main()
{
    LL n;
    while(cin>>n,n)
    {
        LL Z=2,T=4;
        for(;T<n;T<<=1)
        {
            Z++;
        }
        LL z,x,y,ans=0;
        for(z=2;z<=Z;z++)
        {
            for(x=1;;x++)
            {
              LL t=quick_mod(x,z);
              if(t>n/2) break;
              LL l=x+1,r=(LL)pow((double)n,1.0/(double)z);
              while(l<=r)
              {
                  y=(l+r)/2;

                  if(t+quick_mod(y,z)+x*y*z<n)
                    l=y+1;
                  else if(t+quick_mod(y,z)+x*y*z>n)
                          r=y-1;
                  else {
                    ans++;
                    break;
                  }
              }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
给定k，求解x^z+y^z+x*y*z=k所有情况数，约束条件有0<x<y,z>1;

那么我们可以看出x的最小值为1，y的最小值为2，z的最小值为2
由于z作为指数出现了两项，给定k，那么这个指数肯定不能很大
最大也就是31(忽略x^z和x*y*z,只看y^z)
这样，我们可以根据给出的k值，求出一下y最小，也就是为2的时候的z的最大值
那么我们就直到了z的取值范围；
接下我们可以枚举z和x来确定y，获这枚举y和z来确定x
这里我用的方法是枚举x和z的，那么最坏的情况按照z=2,k=2^31来计算，
x的范围就要达到sqrt(k/2),大约为sqrt(10^9),假设z从2到31都按照这个数来计算
(当然实际中要比这个数小),计算次数是sqrt(10^9)*30，是可以接受的

所以我们使用两个枚举，加上二分来确定y就可以了。
y的范围：y最小为x+1，最大由y^z=k来求得(还是放缩)，这样就能解决问题了。

*转载请注明出处，谢谢。
*/


联系
我们