点击打开链接hdu 4282
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代码:
#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;
}
}
}
printf("%d\n" , ans);
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(scanf("%d" ,&k) && k)
solve();
return 0;
}
分享到:
相关推荐
HDU 1022 Train Problem I 附详细思路
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...
The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu_2102_passed_sorce
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码