学步园

题目：http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=612

题意：给一个正整数n，n小于10^8，对于X^X达到n位时，求最小的X，注意是达到n。

分析：先求出第一个满足X^X的位数大于等于n位的X，然后从上到下枚举X，如果X^X的位数小于n时就break。那么i+1就是答案。

题目：http://codeforces.com/contest/325/problem/B

题意：给一个正整数n<=10^18，m是奇数，求的解有多少个，并按从小到大的顺序输出所有的。

分析：方法就是枚举k，二分m。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
typedef long long LL;
const int N = 1005;
const LL INF = 1e18;
const LL R = 3*1e9;

LL S[N];
int cnt;

void Binary_Search(LL n)
{
    for(int k=0;k<63;k++)
    {
        LL l = 1;
        LL r = R;
        if(k >= 30) r = INF >> k;
        while(l <= r)
        {
            LL m = (l + r) >> 1;
            LL ans = (((LL)1 << k) - 1) * m * 2 + m * (m - 1);
            if(ans > 2*n) r = m - 1;
            else if(ans < 2*n) l = m + 1;
            else
            {
                if(m&1) S[cnt++] = m * ((LL)1 << k);
                break;
            }
        }
    }
}

int main()
{
    LL n;
    cin>>n;
    cnt = 0;
    Binary_Search(n);
    sort(S,S+cnt);
    if(cnt == 0) puts("-1");
    else
    {
        for(int i=0;i<cnt;i++)
           cout<<S[i]<<endl;
    }
    return 0;
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4282

题意：对于方程X^Z + Y^Z + XYZ = K，已知K求此方程解的个数，其中要求X<Y，Z>1，而K的范围是0到2^31。

分析：这道题明显的二分搜索题。

首先我们来分析Z的范围：由于X,Y为正整数，X < Y，则1 < X < Y， =====>  Y >= 2

=>  X^Z + Y^Z + XYZ > Y^Z  

=>  2^Z <= Y^Z < 2^31

所以得到2 <= Z<31

对于Z=2时我们来特殊处理。所以只分析Z在3<=Z<31的情况。

我们再来分析X的范围：

对于方程X^Z + Y^Z + XYZ = K， X < Y，则有X^Z + Y^Z + XYZ > 2*X^Z + X*X*Z >= 2*X^3 + 3*X^2

即我们得到：2*X^3 + 3*X^2 < 2^31   解这个方程有：X < 1024

于是现在我们得到了3 <= Z < 31，1 <= X < 1024，当然Z=2特殊处理。接下来就直接枚举X,Z,来二分Y。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>

using namespace std;
typedef long long LL;

LL f[1300][32];

void Init()
{
    for(int i=1; i<1300; i++)
    {
        f[i][0] = 1;
        for(int j=1; j<31; j++)
        {
            f[i][j] = f[i][j-1] * i;
            if(f[i][j] > 2147483648LL)
                break;
        }
    }
}

bool Binary_Search(int x,int z,int K)
{
    int mid;
    int l=x+1;
    int r=1290;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(f[mid][z] == 0)
        {
            r = mid - 1;
            continue;
        }
        LL ret = f[x][z] + f[mid][z] + x * mid * z;
        if(ret < K)
            l = mid + 1;
        else if(ret > K)
            r = mid - 1;
        else
            return true;
    }
    return false;
}

int main()
{
    Init();
    int K;
    while(~scanf("%d",&K),K)
    {
        LL ans = 0;
        int tmp = (int)sqrt(1.0*K);
        if(tmp*tmp == K)
        {
            if(tmp % 2)
                ans += tmp / 2;
            else
                ans += (tmp / 2 - 1);
        }
        for(int x=1; x<1024; x++)
        {
            for(int z=3; z<31; z++)
            {
                if(f[x][z] == 0) break;
                if(Binary_Search(x,z,K))
                    ans++;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}