hdu 4282 A very hard mathematic problem

 
1思路：   枚舉z的范圍(2-31)，然後枚舉x的值1->pow(x,z)>=k/2，最後二分查找y的值即可。
2分析：  1由公式可以知道z的范圍是2-31，但是x和y的范圍不好確定，所以暴力肯定TLE。
               2這種類似的題目一般都是固定兩個然後在二分查找第三個。
               3注意二分查找的時候用到(left+right)/2，所以數據類型要為long long 這樣才不會超出int(這個地方WA了N次，不解釋)，還有二分查找的時候求出當前的值tmp有可能超過long long 范圍，所以還要判斷tmp<0時候說明這時候mid大於y.
               4由於pow函數使用起來比較慢，所以對於大數據來說自己寫個Pow函數，注意返回數據的類型
 
3代碼：
[cpp]
#include<iostream> 
#include<algorithm> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
using namespace std; 
#define MAXN 1010 
 
int k , ans; 
 
long long Pow(long long x , long long y){ 
    long long tmp = x; 
    for(long long i = 1 ; i <  y ; i++) 
       x *= tmp; 
    return x; 
} 
 
void solve(){ 
    int x , y , z; 
    long long  left , right , mid , tmp; 
    ans = 0; 
    for(z = 2 ; z < 32 ; z++){ 
       for(x = 1 ; ; x++){       
          if(Pow(x, z) >= k/2) 
               break; 
          left = x + 1; 
          right = k; 
          while(left <= right){ 
             mid = (left+right)/2; 
             tmp = Pow(x,z)+Pow(mid,z)+mid*x*z; 
             if(tmp == k){             
                ans++; 
                break; 
             } 
             else if(tmp > k|| tmp < 0)/*注意這個地方數據類型的溢出*/       
                right = mid-1; 
             else 
                left = mid+1; 
          } 
       } 
    } www.2cto.com
    printf("%d\n" , ans); 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    while(scanf("%d" ,&k) && k)   
        solve(); 
    return 0; 
}