題目鏈接：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 的范圍，導致判斷大小錯誤。
幸好值溢出時會變負，所以我們可以根據值是否為負來判斷是否溢出。若溢出，直接等效於大於。
[cpp]
#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;
}
