[HNOI2004]高精度开根（高精度，二分）

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N=5e3;
const ll base=1e8;
struct bigint
{
    ll d[N];
    void clear()
    {
        memset(d,0,sizeof(d));
    }
}st,mid;
void print(bigint a)
{
    printf("%lld",a.d[a.d[0]]);
    for(int i=a.d[0]-1;i>0;i--) printf("%08lld",a.d[i]);
    puts("");
}
inline bigint operator *(const bigint &a,const bigint &b)
{
    bigint c;
    c.clear();
    c.d[0]=a.d[0]+b.d[0]-1;
    for(int i=1;i<=a.d[0];i++)
        for(int j=1;j<=b.d[0];j++)
        {
            c.d[i+j-1]+=a.d[i]*b.d[j];
            c.d[i+j]+=c.d[i+j-1]/base;
            c.d[i+j-1]%=base;
        }
    while(c.d[c.d[0]+1]) c.d[0]++,c.d[c.d[0]+1]=c.d[c.d[0]]/base,c.d[c.d[0]]%=base;
    return c;
}
inline bigint operator +(const bigint &a,const bigint &b)
{
    bigint c;
    c.clear();
    c.d[0]=max(a.d[0],b.d[0]);
    for(int i=1;i<=c.d[0];i++)
    {
        c.d[i]+=a.d[i]+b.d[i];
        c.d[i+1]=c.d[i]/base;
        c.d[i]%=base;
    }
    while(c.d[c.d[0]+1]) c.d[0]++,c.d[c.d[0]+1]=c.d[c.d[0]]/base,c.d[c.d[0]]%=base;
    return c;
}
inline bigint operator /(const bigint &a,const int &b)
{
    bigint c;
    c.clear();
    c.d[0]=a.d[0];
    int res=0;
    for(int i=a.d[0];i>0;i--)
    {
        res=res*base+a.d[i];
        c.d[i]=res/b;
        res%=b;
    }
    while(!c.d[c.d[0]]) c.d[0]--;
    return c;
}
inline bool operator <=(const bigint &a,const bigint &b)
{
    if(a.d[0]!=b.d[0]) return a.d[0]<b.d[0];
    for(int i=a.d[0];i;i--)
        if(a.d[i]!=b.d[i]) return a.d[i]<b.d[i];
    return 1;
}
bigint qpow(bigint x,int y)
{
    bigint a;
    a.clear();
    a.d[0]=a.d[1]=1;
    while(y)
    {
        if(y&1) a=a*x;
        x=x*x,y>>=1;
    }
    return a;
}
int m;
const int M=1e4+10;
char s[M];
int main()
{
    scanf("%d",&m);
    scanf("%s",s);
    if(m==1)
    {    
        printf("%s",s);
        return 0;
    }
    int len=strlen(s);
    st.clear();
    for(int i=len-1;i>=0;i-=8)
    {
        ll now=0;
        for(int j=max(i-7,0);j<=i;j++)
            now=now*10+(s[j]-‘0‘);
        st.d[++st.d[0]]=now;
    }
    bigint l,r,dw2;
    l.clear(),r.clear(),dw2.clear();
    l.d[0]=1,r.d[0]=r.d[1]=1,dw2.d[0]=1,dw2.d[1]=2;
    while(qpow(r,m)<=st) l=r,r=r*dw2;
    while(l+dw2<=r)
    {
        mid=(l+r)/2;
        if(qpow(mid,m)<=st) l=mid;
        else r=mid;
    }
    if(qpow(l,m)<=st) print(l);
    else print(r);
    return 0;
}