首页 > 代码库 > 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 大整数(高精不熟的一定要做!)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。