题目链接：

http://poj.org/problem?id=2109

参考：

http://blog.csdn.net/code_pang/article/details/8263971

题意：

给定n,p，求k使得kn=p(1≤n≤200, 1≤p<10101, 1≤k≤109)

分析：

高精度+二分~~

k的位数为p的位数除以n的向上取整，这样知道k的位数便可以在范围内二分了~注意这里的答案是向下取整~~

代码：

#include<cstring>

#include<cstdio>

#include<cmath>

#include<cstdlib>

using namespace std;

#define MAXN 9999

#define MAXSIZE 1000

#define DLEN 4

const int maxn = 205;

char p[maxn];

class BigNum

 {

    private:

        int a[500];

        int len;

    public:

        BigNum(){

            len = 1;

            memset(a, 0 ,sizeof(a));

        }

        BigNum(const int);

        BigNum(const char*);

        BigNum(const BigNum &);

        BigNum &operator = (const BigNum &);

        BigNum operator +(const BigNum &)const ;

        BigNum operator*(const BigNum &)const ;

        BigNum operator^(const int &)const ;

        bool operator >(const int &)const;

        bool operator >(const BigNum &T)const;

        void print();

 };

 BigNum::BigNum(const int b)

 {

     int c, d = b;

     len = 0;

     while(d > MAXN){

        c = d % (MAXN + 1);

        d = d / (MAXN + 1);

        a[len++] = c;

     }

     a[len++] = d;

 }

BigNum::BigNum(const char*s)

{

    int t, k, index;

    memset(a,0,sizeof(a));

    int l = strlen(s);

    len = l / DLEN;

    if(l % DLEN)

        len++;

    index=0;

    for(int i = l - 1; i >= 0; i -= DLEN){

        t = 0;

        k = i - DLEN + 1;

        if(k<0) k=0;

        for(int j = k; j <= i; j++)

            t = t * 10 + s[j] - '0';

        a[index++] = t;

    }

}

BigNum::BigNum(const BigNum & T) : len(T.len)

{

    memset(a, 0, sizeof(a));

    for(int i = 0 ; i < len ; i++)

        a[i] = T.a[i];

}

BigNum & BigNum::operator=(const BigNum & n)

{

    len = n.len;

    memset(a, 0, sizeof(a));

    for(int i = 0 ; i < len ; i++)

        a[i] = n.a[i];

    return *this;

}

BigNum BigNum::operator+(const BigNum & T) const

{

    BigNum t(*this);

    int big;      //位数

    big = T.len > len ? T.len : len;

    for(int i = 0; i < big; i++){

        t.a[i] +=T.a[i];

        if(t.a[i] > MAXN){

            t.a[i + 1]++;

            t.a[i] -=MAXN+1;

        }

    }

    if(t.a[big] != 0)  t.len = big + 1;

    else t.len = big;

    return t;

}

BigNum BigNum::operator*(const BigNum & T) const

{

    BigNum ret;

    int up;

    int temp,temp1;

    int i, j;

    for(i = 0 ; i < len ; i++){

        up = 0;

        for(j = 0 ; j < T.len ; j++){

            temp = a[i] * T.a[j] + ret.a[i + j] + up;

            if(temp > MAXN){

                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);

                up = temp / (MAXN + 1);

                ret.a[i + j] = temp1;

            }

            else{

                up = 0;

                ret.a[i + j] = temp;

            }

        }

        if(up != 0)

            ret.a[i + j] = up;

    }

    ret.len = i + j;

    while(ret.a[ret.len - 1] == 0 && ret.len > 1)

        ret.len--;

    return ret;

}

BigNum BigNum::operator^(const int & n) const

{

    BigNum t,ret(1);

    if(n < 0)  exit(-1);

    if(n == 0)  return 1;

    if(n == 1) return *this;

    int m = n;

    int i;

    while(m > 1){

        t = *this;

        for(i = 1; i<<1<=m; i <<= 1)

            t = t * t;

        m -= i;

        ret = ret * t;

        if(m == 1) ret=ret*(*this);

    }

    return ret;

}

bool BigNum::operator>(const BigNum & T) const

{

    int ln;

    if(len > T.len)

        return true;

    else if(len == T.len){

        ln = len - 1;

        while(a[ln] == T.a[ln] && ln >= 0)

            ln--;

        if(ln >= 0 && a[ln] > T.a[ln])

            return true;

        else

            return false;

    }

    else

        return false;

}

bool BigNum::operator >(const int & t) const

{

    BigNum b(t);

    return *this>b;

}

void BigNum::print()

{

    printf("%d",a[len-1]);

    for(int i = len - 2 ; i >= 0 ; i--)  printf("%04d",a[i]);

    printf("\n");

}

int main(void)

{

    int n, len, MIN, MAX, MID;

    while(~scanf("%d%s", &n, &p)){

        len = (int)ceil((double)strlen(p) / n);

        MIN = 1, MAX = 9;

        for(int i = 0; i < len - 1; i++){

            MAX *= 10;

            MAX += 9;

            MIN *= 10;

        }

        while(MIN < MAX){//[]

            MID = (MIN + MAX) / 2;

            if(BigNum(p) > (BigNum(MID) ^ n)) MIN = MID +1;

            else if((BigNum(MID) ^ n) > BigNum(p)) MAX = MID - 1;

            else break;

        }

        if(MAX == MIN)  MID = MIN;

        if((BigNum(MID) ^ n) > BigNum(p)) MID--;

         printf("%d\n",MID);

    }

    return 0;

}

代码：

double类型能表示10−307到10308, 足够这个题用。

而double超过16位后面都变成0，这样正好满足向下取整。

12337=4332529576639313702577

12347=4357186184021382204544

12357=4381962969567270546875

值不同的地方（从高到低第三位）没有超过double的精度，所以不会导致错误答案~

#include<iostream>

#include<cmath>

using namespace std;

int main (void)

{

    double n, m;

    while(cin>>n>>m){

        cout<<pow(m, 1/n)<<endl;

    }

    return 0;

}

//或者

#include<iostream>

#include<cmath>

using namespace std;

int main (void)

{

    double n, p;

    while(cin>>n>>p){

         cout<< exp(log(p)/n) <<endl;

    }

    return 0;

}

//pow明显更快，只是想说明有时候取对数也是个不错的方法~