当前位置:编程学习 > C/C++ >>

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.zzzyk.com
    printf("%d\n" , ans); 

 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    while(scanf("%d" ,&k) && k)   
        solve(); 
    return 0; 

 
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,