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++ ,