首页 > 代码库 > vijos P1375 大整数(高精不熟的一定要做!)

vijos P1375 大整数(高精不熟的一定要做!)

/*我尼玛这题不想说啥了亏了高精写的熟.....加减乘除max都写了高精二分 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 1010#define memcpy(a,b); for(int i=0;i<=1000;i++)a[i]=b[i];using namespace std;int n[maxn],len,l[maxn],r[maxn],mid[maxn],ans[maxn];char s[maxn];void Plus(int a[maxn],int b[maxn]){    int L=max(a[0],b[0]);    int c[maxn];memset(c,0,sizeof(c));    for(int i=1;i<=L;i++)        c[i]=a[i]+b[i];    for(int i=1;i<=L;i++)        if(c[i]>9){c[i+1]++;c[i]%=10;}    if(c[L+1])L++;c[0]=L;    memcpy(a,c);}void Sub(int a[maxn]){    a[1]--;    int p=1;    while(a[p]<0){        a[p]=9;p++;a[p]--;    }    if(a[a[0]]==0)a[0]--;}void Mul(int a[maxn],int b[maxn]){    int c[maxn];memset(c,0,sizeof(c));    int l1=a[0],l2=b[0],l3=l1+l2;    for(int i=1;i<=l1;i++){          int x=0;          for(int j=1;j<=l2;j++){              c[j+i-1]+=a[i]*b[j]+x;            x=c[i+j-1]/10;            c[i+j-1]=c[i+j-1]%10;        }        c[i+l2]=x;    }    int k=0;    for(int i=l3;i>=0;i--)        if(c[i]){k=i;break;}    c[0]=k;memcpy(a,c);}void Div(int a[maxn],int x){    int b[maxn],c=0;memset(b,0,sizeof(b));    for(int i=a[0];i>=1;i--){        b[i]=(c*10+a[i])/x;c=a[i]%x;    }    int k=0;    for(int i=a[0];i>=0;i--)        if(b[i]){k=i;break;}    b[0]=k;memcpy(a,b);}bool Cmp(int a[maxn],int b[maxn]){    if(a[0]<b[0])return 1;    else if(a[0]>b[0])return 0;    for(int i=a[0];i>=1;i--){        if(a[i]<b[i])return 1;        if(a[i]>b[i])return 0;    }    return 1;}void Cal(int x[maxn]){    int a[maxn],b[maxn],c[maxn],d[maxn],e[maxn];    e[0]=1;e[1]=3;memset(a,0,sizeof(a));    memcpy(b,x);memcpy(c,x);memcpy(d,x);    Mul(b,x);Mul(b,x);Mul(c,x);Mul(d,e);    Plus(a,b);Plus(a,c);Plus(a,d);    memcpy(x,a);}bool Judge(int a[maxn]){    int b[maxn];memcpy(b,a);    Cal(b);    return Cmp(b,n);}void cal(int a[maxn]){    int b[maxn],c[maxn];    memcpy(b,l);memcpy(c,r);    Plus(b,c);Div(b,2);    memcpy(a,b);}int main(){    scanf("%s",s);    len=strlen(s);    for(int i=1;i<=len;i++)        n[i]=s[len-i]-0;    n[0]=len;    l[0]=1;r[0]=50;    for(int i=1;i<=50;i++)r[i]=1;    while(Cmp(l,r)){        cal(mid);int a[maxn];        memset(a,0,sizeof(a));        a[0]=1;a[1]=1;        if(Judge(mid)){            memcpy(l,mid);            Plus(l,a);            memcpy(ans,mid);        }        else{            memcpy(r,mid);            Sub(r);        }    }    for(int i=max(ans[0],1);i>=1;i--)        printf("%d",ans[i]);    return 0;}

 

vijos P1375 大整数(高精不熟的一定要做!)