P2293 [HNOI2004]高精度开根

bzoj1213  

为了证明我不是毒瘤 于是我把这道题打了 很艰难

结果一看最后那个题解 居然要乘10来确保精度 惊了？！

然后还改进了一下自己的高精模版

#include<bits/stdc++.h>
using namespace std;
#define rg register
const int N=10000+5,power=4,base=10000;
int n;
char s[N];
struct num{
    int a[N>>1];
    num(){memset(a,0,sizeof(a));}
    num(char *s)
    {
        memset(a,0,sizeof(a));
        int len=strlen(s);
        a[0]=(len+power-1)/power;
        for(rg int i=0,t=0,w;i<len;++i,w*=10)
        {
            if(i%power==0) w=1,++t;
            a[t]+=w*(s[i]-'0');
        }
    }
    void print()
    {
        printf("%d",a[a[0]]);
        for(rg int i=a[0]-1;i>0;--i) printf("%0*d",power,a[i]);
    }
}l,r,a,e,tw,mid,m,ten;

num operator +(const num &p,const num &q)
{
    num c;
    c.a[0]=max(p.a[0],q.a[0]);
    for(rg int i=1;i<=c.a[0];++i)
        c.a[i]+=p.a[i]+q.a[i];
    for(rg int i=1;i<=c.a[0]+1;++i)
    if(c.a[i]>=base) c.a[i+1]+=c.a[i]/base,c.a[i]%=base;
    if(c.a[c.a[0]+1]) ++c.a[0];
    return c;
}

bool operator <(const num &p,const num &q)
{
    if(p.a[0]<q.a[0]) return 1;
    if(p.a[0]>q.a[0]) return 0;
    for(rg int i=p.a[0];i>0;--i)
    if(p.a[i]!=q.a[i]) return p.a[i]<q.a[i];
    return 0;
}

num operator *(const num &p,const num &q)
{
    num c;
    c.a[0]=p.a[0]+q.a[0]-1;
    for(rg int i=1;i<=p.a[0];++i)
    for(rg int j=1;j<=q.a[0];++j)
        c.a[i+j-1]+=p.a[i]*q.a[j];
    for(rg int i=1;i<=c.a[0]+1;++i)
    if(c.a[i]>=base) c.a[i+1]+=c.a[i]/base,c.a[i]%=base;
    if(c.a[c.a[0]+1]) ++c.a[0];
    return c;
}

num operator /(const num &p,const int &q)//高精/低精
{
    if(q==1) return p;
    num x;
    int y=0;
    for(rg int i=p.a[0];i>=1;--i)
    {
        y=y*base+p.a[i];
        if(y>=q) x.a[i]=y/q,y%=q;
    }
    x.a[0]=p.a[0];
    while(x.a[0]>=1&&!x.a[x.a[0]]) --x.a[0];//去前导0
    return x;
}

bool operator ==(const num &p,const num &q)
{
    if(p.a[0]!=q.a[0]) return 0;
    for(rg int i=p.a[0];i>0;--i) if(p.a[i]!=q.a[i]) return 0;
    return 1;
}

num fpower(num x,int b)
{
    num res=e;
    while(b)
    {
        if(b&1) res=res*x;
        x=x*x,b>>=1;
    }
    return res;
}

int main()
{
    freopen("in.txt","r",stdin);
    e.a[0]=1,e.a[1]=1,tw.a[0]=1,tw.a[1]=2,ten.a[0]=1,ten.a[1]=10;
    scanf("%d%s",&n,s);
    reverse(s,s+strlen(s));
    a=num(s);r=e;
    if(n==1) {a.print();return 0;}
    while(fpower(r,n)<a) l=r,r=r*tw;
    a=a*fpower(ten,n),l=l*ten,r=r*ten;
    while((l+e)<r)
    {
        mid=(l+r)/2;
        if(fpower(mid,n)<a) l=mid;
        else r=mid;
    }
    if(fpower(r,n)==a) r=r/10,r.print();
    else l=l/10,l.print();
    return 0;
}