说到高精度问题，想来众多oier都是深恶痛绝的。
最为可怕的有两种，一种是明摆着高精度算法，而原理极其简单的一类题。例如CQOI2005（老题了）最小公倍数，强行将高精度除法推到了题面，Orz。
另外一种是强行在题目推导结果的过程中溢出2^63。。。这一类题蒟蒻还没见过，但是经常听到大神对于这种题型不屑的评论。
话不多说，上代码。自带大常数的高精度，高精度除法还压不来位。。。风格迥异。
//by:Hzyuer //高精度个人模版——（2017.3.7） //使用string类型作为输入输出。 //string类型自带大常数，请小心使用 //通用万进制,支持正负数 //负数有可能出错。。。小心食用 #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int mod=10000;//进制 const int Size=10000;//数组大小 string a,b; inline void Change_Num(string b,long long rec[]){//字符串转换为数组 int f=0; string a; if(b[0]=='-'){f=1; for(int i=1;i<b.length();i++)a+=b[i]; }else a=b; int len=a.length(),i,j; rec[0]=(len+log10(mod)-1)/log10(mod);//转换万进制 for(i=0;i<len;i++){ j=(len-i+log10(mod)-1)/log10(mod); rec[j]=rec[j]*10+a[i]-'0'; } if(f)rec[rec[0]+1]=1; return ; } inline void Change_String(long long a[],string &rec){//数组转换为字符串 int i,j,p;string temp; if(a[a[0]+1])rec+='-'; p=a[a[0]]; while(p)temp+=p+'0',p/=10; for(i=temp.length()-1;i>=0;i--)rec+=temp[i]; for(i=a[0]-1;i>=1;i--){ temp="0000"; p=a[i]; for(j=3;j>=0&&p;j--){ if(p)temp[j]=p+'0'; p/=10; } rec+=temp; } if(rec.empty())rec="0"; return ; } inline int Cmp(string x,string y){ string a,b; int f=0,i; if(x[0]=='-'&&y[0]!='-')return 2; if(x[0]!='-'&&y[0]=='-')return 1; if(x.length()>y.length()){if(x[0]!='-')return 1;return 2;} if(x.length()<y.length()){if(x[0]!='-')return 2;return 1;} if(x[0]=='-'){ for(i=1;i<x.length();i++)a+=x[i]; for(i=1;i<y.length();i++)b+=y[i]; f=1; }else a=x,b=y; if(a>b){ if(f)return 2; else return 1; } if(a<b){ if(f)return 1; else return 2; } return 0; } inline int Abs_Cmp(string x,string y){ string a,b; if(x[0]=='-')for(int i=1;i<x.length();i++)a+=x[i];else a=x; if(y[0]=='-')for(int i=1;i<y.length();i++)b+=y[i];else b=y; if(a.length()>b.length())return 1; if(a.length()<b.length())return 2; if(a>b)return 1;if(a<b)return 2;return 0; } string Sub(string x,string y); string Plus(string x,string y); string Time(string x,string y); string Div(string x,string y,int type); inline bool judge(string s){for(int i=0;i<s.size();i++)if(s[i]!='0')return false;return true;} string Gcd(string a,string b){ string t; while(!judge(b)){t=a;a=b;b=Div(t,b,2);} return a; } int main(){ cin>>a>>b; /* cout<<Plus(a,b)<<endl; cout<<Sub(a,b)<<endl; cout<<Time(a,b)<<endl; cout<<Div(a,b,1)<<" "<<Div(a,b,2)<<endl; */cout<<Gcd(a,b)<<endl; return 0; } string Plus(string x,string y){// x+y problem if(x[0]=='-'&&y[0]!='-'){ string a; for(int i=1;i<x.length();i++)a+=x[i]; return Sub(y,a); } if(y[0]=='-'&&x[0]!='-'){ string a; for(int i=1;i<y.length();i++)a+=y[i]; return Sub(x,a); } string ans;int f=0; long long a[Size],b[Size]; Change_Num(x,a);Change_Num(y,b); if(a[a[0]+1]){a[a[0]+1]=0;b[b[0]+1]=0;f=1;} a[0]=max(a[0],b[0]); for(int i=1;i<=a[0];i++){ a[i]+=b[i]; if(a[i]>=mod) a[i+1]+=a[i]/mod,a[i]%=mod; } if(a[a[0]+1])a[0]++; if(f)a[a[0]+1]=1; Change_String(a,ans); return ans; } string Sub(string x,string y){// x-y preblem if(x[0]=='-'&&y[0]=='-'){ string a,b; for(int i=1;i<x.length();i++)a+=x[i]; for(int i=1;i<y.length();i++)b+=y[i]; return Sub(b,a); } if(x[0]=='-'&&y[0]!='-'){ string a;a+='-'; for(int i=0;i<y.length();i++)a+=y[i]; return Plus(x,a); } if(x[0]!='-'&&y[0]=='-'){ string a; for(int i=1;i<y.length();i++)a+=y[i]; return Plus(x,a); } int f=0; if(x<y){swap(x,y);f=1;} string ans; long long a[Size],b[Size]; Change_Num(x,a);Change_Num(y,b); a[a[0]+1]=0;b[b[0]+1]=0; for(int i=1;i<=a[0];i++){ if(a[i]<b[i]) a[i]+=mod,a[i+1]--; a[i]-=b[i]; } while(a[0]&&(!a[a[0]]))a[0]--; if(f)a[a[0]+1]=1; Change_String(a,ans); return ans; } string Time(string x,string y){// x*y problem string ans; if(x[0]=='0'||y[0]=='0'){ans+='0';return ans;} int f=0; if(x[0]=='-')f^=1; if(y[0]=='-')f^=1; long long a[Size],b[Size],c[Size*2],i,j; Change_Num(x,a);Change_Num(y,b); a[a[0]+1]=0;b[b[0]+1]=0; for(i=1;i<=a[0];i++) for(j=1;j<=b[0];j++) c[i+j-1]+=a[i]*b[j]; c[0]=a[0]+b[0]; for(i=1;i<=c[0];i++)c[i+1]+=c[i]/mod,c[i]%=mod; while(c[0]&&(!c[c[0]]))c[0]--; if(f)c[c[0]+1]=1; Change_String(c,ans); return ans; } int D_sub(int *a,int *b,int Len_a,int Len_b){ if(Len_a<Len_b)return -1; if(Len_a==Len_b){ for(int i=Len_a-1;i>=0;i--) if(a[i]>b[i]) break; else if(a[i]<b[i]) return -1; } for(int i=0;i<Len_a;i++){ a[i]-=b[i]; if(a[i]<0) a[i]+=10,a[i+1]--; } for(int i=Len_a-1;i>=0;i--) if(a[i]) return i+1; return 0; } string Div(string x,string y,int type){// x/y problem if(y[0]=='0')exit(0); string p,q,rest,ans; int f=0; if(x[0]=='-'){ for(int i=1;i<x.length();i++)p+=x[i];f^=1; }else p=x; if(y[0]=='-'){ for(int i=1;i<y.length();i++)q+=y[i];f^=1; }else q=y; int a[Size],b[Size],c[Size],Len_a=p.size(),Len_b=q.size(),i,j,aaa=Len_a; memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c)); for(i=Len_a-1;i>=0;i--)a[Len_a-1-i]=p[i]-'0'; for(i=Len_b-1;i>=0;i--)b[Len_b-1-i]=q[i]-'0'; if(Len_a<Len_b||(Len_a==Len_b&&p<q))return p; int t=Len_a-Len_b,temp; for(i=Len_a-1;i>=0;i--)if(i>=t)b[i]=b[i-t];else b[i]=0; Len_b=Len_a; for(int j=0;j<=t;j++) while((temp=D_sub(a,b+j,Len_a,Len_b-j))>=0){Len_a=temp;c[t-j]++;} for(i=0;i<Size-10;i++)c[i+1]+=c[i]/10,c[i]%=10; while(!c[i])i--;if(f)ans+='-'; while(i>=0)ans+=c[i--]+'0'; i=aaa; while(!a[i])i--; while(i>=0)rest+=a[i--]+'0'; if(rest.empty())rest="0"; if(x[0]=='-'&&rest!="0")rest='-'+rest; if(type==1)return ans; if(type==2)return rest; }
