HDU 4282 A very hard mathematic problem 2分

HDU 4282 A very hard mathematic problem 二分

来源：http://acm.hdu.edu.cn/showproblem.php?pid=4282

题意：给出一个数n，问x^z + y^z + x*y*z = n有多少这样的x y z，其中y > x,z > 1,x,y,z都是正数。

思路：注意到z最大为31，x最大为50000，因此可以枚举x,z,二分判断y即可。

代码：

#include <iostream>
#include <vector>
#include <cstdio>
#include <string.h>
#include <vector>
#include <climits>
using namespace std;

const int N = 50010;
__int64 aa[N][35];
__int64 mi(int x,int cnt){
	__int64 s = 1;
	for(int i = 1; i <= cnt; ++i)
		s *= x;
	return s;
}
void init(){
	memset(aa,-1,sizeof(aa));
	for(int i = 1; i < N; ++i){
		for(int j = 2; j <= 31; ++j){
		   __int64 x = mi(i,j);
		   if(x >= INT_MAX || x < 0)
			   continue;
		   aa[i][j] = x;
		}
	}
}
int main(){
	//freopen("1.txt","r",stdin);
	init();
	int n;
	while(scanf("%d",&n) && n){
		int ans = 0;
		for(int x = 1; x < N; ++x){
			for(int z = 2; z <= 31; ++z){
				if(aa[x][z] == -1)
					break;
				int lp = 2,rp = N - 1;
				bool flag = false;
				while(lp <= rp){
				   int mid = (lp + rp) / 2;
				   if(aa[mid][z] == -1){
				     rp = mid - 1;
					 continue;
				   }
				   __int64 sum = aa[x][z] + mi(mid,z) + x*mid*z;
				   if(sum == n ){
					   if(mid > x){
					     flag = true;
					     break;
					   }
					   rp = mid - 1;
				   }
				   else if(sum < n){
				     lp = mid + 1;
				   }
				   else{
				     rp = mid - 1;
				   }
				}
				if(flag) ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}