HDU 4282 A very hard mathematic problem 2 분 문제
7082 단어 Math
해제:http://www.cnblogs.com/E-star/archive/2012/09/11/2680992.html
View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#define CL(a,num) memset((a),(num),sizeof(a))
#define iabs(x) ((x) > 0 ? (x) : -(x))
#define Min(a,b) (a) > (b)? (b):(a)
#define Max(a,b) (a) > (b)? (a):(b)
#define ll __int64
#define MOD 100000007
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define test puts("<------------------->")
#define maxn 100007
#define M 100007
#define N 107
using namespace std;
//freopen("din.txt","r",stdin);
ll inf = 2147483648ll;
ll Pow(int a,int b){
ll sum = 1;
for (int i = 1; i <= b; ++i) sum *= a;
return sum;
}
bool Bsearch(int L,int R,int x,int z,int k,ll POW){
int l = L, r = R;
while (l <= r){
int m = (l + r)>>1;
ll tmp = POW + Pow(m,z) + (ll)x*m*z;
if (tmp < 0) r = m -1;// ll wa
else if (tmp == k) return true;
else if (tmp < k) l = m + 1;
else r = m - 1;
}
return false;
}
int main(){
//freopen("din.txt","r",stdin);
int K;
while (~scanf("%d",&K)){
if (!K) break;
int ans = 0;
for (int x = 1; x < 50000 && x < K; ++x){// x
for (int z = 2; z < 31; ++z){// Z
ll tmp = Pow(x,z);
if (tmp > K) break;
int mk = Bsearch(x + 1,50000,x,z,K,tmp);// y
if (mk) ans++;
}
}
printf("%d
",ans);
}
}