题解 P2293 【[HNOI2004]高精度开根】

· · 题解

思路就是二分+快速幂；

这是我的非重载运算符的高精模版

http://blog.csdn.net/largecub233/article/details/57410304

如果失效了说明我更新模版了，可以到我博客里找；

我的博客：http://blog.csdn.net/largecub233

没写全，我会完善的（比如负数）；

如果上面的程序有问题，请告诉我；

目前fop_zz已经发现了我高精模版的一个bug感谢；

然后对于这道题，毒瘤题；

一定要高精压位；

我压1e9的；用unsigned long long 存；

大家不要这样。1e8就好了；

什么是压位；

比如一个数；

123456789

我压4位；就是

6789、、

2345、、

1、、

这样运算，会比十进制快；

比如 12000078

压好就是

78、、

1200、、

所以我们输出时要搞好前导0；

输出前导0还要特判本身就是0的情况；

然后，

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define Ll unsigned long long
using namespace std;
const Ll NN=1e9;
const int N=9;
struct H{
    Ll a[1500],len;
    H(){memset(a,0,sizeof a);len=1;}
};
int n;
H s;
void init(H &a){//读入 
    string s; cin>>s; 
    int l; 
    a.len=0;
    for(int r=s.length()-1;r>=0;r-=N){
        a.len++;                      
        if(r>=N-1)l=r-N+1;else l=0;
        for(int i=l;i<=r;i++)a.a[a.len]=a.a[a.len]*10+s[i]-48;
    }
}  
void outit(H a){//输出 
    printf("%d",a.a[a.len]);
    for(int i=a.len-1;i;i--){
        for(int k=NN/10;a.a[i]<k;k/=10)printf("0");
        if(a.a[i])printf("%d",a.a[i]); 
    }printf("\n");    
}
void in(H &a,int x){//赋值 
    if(!x)return;
    a.len=0;
    while(x){a.a[++a.len]=x%NN;x=x/NN;}
}
bool bigD(H a,H b){//比较是否大于等于 
    if(a.len>b.len)return 1;
    if(a.len<b.len)return 0;
    for(int i=a.len;i;i--)
        if(a.a[i]!=b.a[i])
            if(a.a[i]>b.a[i])return 1;else return 0;
    return 1;
}
H jia(H a,H b){//加法 
    H c;
    int l=max(a.len,b.len);
    for(int i=1;i<=l;i++){
        c.a[i]+=a.a[i]+b.a[i];
        c.a[i+1]=c.a[i]/NN;
        c.a[i]%=NN;
    }
    if(c.a[l+1])l++;
    c.len=l;
    return c;
}
H chu(H a){//除法 
    H c;
    if(a.len==1){c.a[1]=a.a[1]>>1;return c;}
    for(int i=a.len;i;i--){
        if(a.a[i]&1ll)a.a[i-1]+=NN;
        c.a[i]=a.a[i]>>1;
    }
    if(c.a[a.len])c.len=a.len;else c.len=a.len-1;
    return c;
}
H rrr(H a){//-1操作 
    if(a.len==1){
        a.a[1]--;return a;
    }
    H c=a;
    c.a[1]--;
    int l=1;
    while(c.a[l]<0){
        c.a[l]=NN-1;
        c.a[++l]--;
    }
    if(!c.a[c.len])c.len--;
    return c;
}
H chen(H a,H b){//乘法 
    H z;
    z.len=a.len+b.len+2;
    for(int i=1;i<=a.len;i++)
    for(int j=1;j<=b.len;j++)z.a[i+j-1]+=(a.a[i]*b.a[j]);
    for(int i=1;i<=z.len;i++)z.a[i+1]+=z.a[i]/NN,z.a[i]%=NN; //取mo慢，放到外面取   
    while(z.len>1&&!z.a[z.len])z.len--;
    return z;
}
H ksm(H a,int n){//快速幂 
    if(n==1)return a;
    H c=ksm(a,n>>1);
    c=chen(c,c);
    if(n&1)c=chen(c,a);
    return c;
}
bool Chu(H a){//本来这个函数名是骂出题人的，怕和谐，就改了 
    if(a.len*n-n+1>s.len)return 0;
    if(bigD(s,ksm(a,n)))return 1;
    return 0;
}
int main(){
//    freopen("calc.in","r",stdin);
//    freopen("calc.out","w",stdout);
    scanf("%d",&n);
    init(s);
    if(n==1){outit(s);return 0;}
    H l,r,mid,ans;
    in(l,1);
    r=s;
    while(bigD(r,l)){
        mid=jia(l,r);
        mid=chu(mid);
        if(Chu(mid)){
            if(bigD(mid,ans))ans=mid;
            H c;
            in(c,1);
            l=jia(mid,c);
        }else r=rrr(mid);         
    }
    outit(ans);
}