题目链接“:
?pid=4282
题意:
给定一个方程式:x^z + y^z + x*y*x = k;
对于给定的k,有多少个三元组(x,y,z)
使这个方程成立。
其中 0<x<y, z<1 ,k<2^32;
x,y,z,都是正整数。
分析:
现根据题目的范围和方程的结构可以先预测一下每个数的范围。
2<=z<=32 , 1<=x<y<2^16;
然后我们在分析一下方程。发现当,,其中任意两个数固定的时候
这个方程的左边都是单调递增的。因此我们可以枚举其中的两个
然后二分判断另外一个存不存在。为了方便我们可以枚举z,y.
二分判断x.
代码如下:
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;typedef long long LL;LL k;LL quick(LL a,LL b){LL tmp =1;for(int i=0;i<b;i++){tmp=tmp*a;if(tmp>=k) return -1;}return tmp;}LL calu(LL x,LL y,LL z){return quick(x,z)+quick(y,z)+x*y*z;}bool bin_search(LL y,LL z){LL low = 1,high = y,mid;while(low<high){mid=(low+high)>>1;LL tmp = calu(mid,y,z);//cout<<"mid "<<mid<<endl;//cout<<"tmp "<<tmp<<endl;if(tmp==k) return true;else if(tmp<k) low=mid+1;else high =mid;}return false;}int main(){while(~scanf("%lld",&k)&&k!=0){if(k==1||k==2){puts("0");continue;}LL INF = (LL) sqrt(k*1.0);LL cnt=0;for(LL z = 2;z<=32;z++){for(LL y = 2;y<=INF;y++){LL tmp = quick(y,z);if(tmp == -1) break;if(bin_search(y,z))cnt++;}}printf("%I64d\n",cnt);}return 0;}
期待遇上一位撑着油纸伞,结着忧愁丁香一样的姑娘;或者在春暖花开时,