HDU 4282 A very hard mathematic problem（12年天津网络赛-数学）
题目链接：Click here~~
题意：
给你一个式子 x^z + y^z + x*y*z = k，k 为给定的某个 int 范围内的数字。
求共有多少组关于 x,y,z 的解。（0< x < y,z > 1）
解题思路：
这题纠结了2天，我擦。今天终于把错误拍出来了。
观察式子不难发现，显然当 z 越大的时候 x,y 的值越小。
由于 y 最小等于2，所以有 2^z < k，又k < 2^31，所以有 z < 31。
1、首先考虑当 z=2 的时候，式子左边可以化为 (x+y)^2 = k 的形式。
所以当 k 是完全平方数的时候，(x,y) 才有可能有解。
假如 m^2 = k ，问题就相当于求 x+y = m (x < y) 的解的组数。
容易得出，当m为偶数时，解组数为 m/2-1；当m为奇数时，解组数为 (m-1)/2。
2、然后考虑当 z>=3 的时候。
当 z=3 的时候，x,y 可能取到的值最大，而稍加计算可以得出 y 的最大值是1290.xx，设这个值为M。
那么枚举x,z的复杂度变为O(M*30)，大概是O(10^4)。
如果再直接枚举y的话，复杂度为O(M^2 *30)，大概是O(10^7)，略大。（不过也能140MS AC）。
那么有没有好的方法呢?
显然当 x,z 确定后，式子关于 y 是单调递增的，于是可以二分，将复杂度降为O(M*logM*30)，大概是O(10^5)。（15MS AC）。
第一次用小号交的，爆了0MS，然后竟然排到了rank1。O(∩_∩)O...
Ps：思路一直都是对的，可是昨天WA了一天。
这种题要注意一些细节。在二分的时候，我 y 的右边界一直取的是当 z = 3的时候的 M。这种贪方便的做法会引发一个问题。
就是当 z 逐渐变大的时候，二分区间中很多的值会溢出long long 的范围，导致判断大小错误。
幸好值溢出时会变负，所以我们可以根据值是否为负来判断是否溢出。若溢出，直接等效于大于。
#include <stdio.h>#include <math.h>typedef __int64 LL;int k,x,y,z;LL xz,yz;LL myPow(int a,int n){ LL ans = a; while(--n) ans *= a; return ans;}LL fun(int Y){ return xz + yz + x*Y*z;}bool FindIt(int l,int r){ while(l <= r) { int mid = (l+r)/2; yz = myPow(mid,z); LL f = fun(mid); if(f == k) return true; if(f<0 || f>k) r = mid-1; else l = mid+1; } return false;}int main(){ while(scanf("%d",&k),k) { int ans = 0; int sq = sqrt(k*1.0); if(sq*sq == k) ans += (sq-1)/2; for(z=3;z<31;z++) { for(x=1;;x++) { xz = myPow(x,z); if(xz >= k/2) break; if(FindIt(x+1,1300)) ans++; } } printf("%d\n",ans); } return 0;}