两个大数，求其最大公约数（小于2^1000）

#include<iostream> #include<cstdio> #include<cmath> #include<string.h> #include<string> #include<algorithm> #include <vector> using namespace std; int judge(string a,string b){//////判断前 b.size() 位 ，a 与 b 的大小 ? ? if(a.size()==b.size()){ ? ? ? ? for(vector<string>::size_type i=0;i<a.size();i++) ? ? ? ? ? ? if(b[i]>a[i]) return -1; ? ? ? ? return 1; ? ? } ? ? for(vector<string>::size_type i=0;i<b.size();i++) ? ? ? ? if(b[i]>a[i]) return 0; ? ? return 1; } string fan1(string a,string b,int i,int j){/////////二进制减法 ? ? string s; ? ? int flag=0,k=0,p=i+1; ? ? char ch[2009]; ? ? for( ; i>=0 && j>=0; i--,j--){ ? ? ? ? if(!flag){ ?/////////没有借过位 ? ? ? ? ? ? if(a[i]>= b[j]) ? ? ? ? ? ? ? ? ch[k++]='0'+(a[i]-b[j]); ? ? ? ? ? ? else { ? ? ? ? ? ? ? ? ch[k++]=b[j]; ? ? ? ? ? ? ? ? if(a[i-1]=='0') flag=1; ? ? ? ? ? ? ? ? else a[i-1]--; ? ? ? ? ? ? } ? ? ? ? ? ? continue; ? ? ? ? } ? ? ? ? //////////////////////////借位 ? ? ? ? if(a[i]==b[j]){ ? ? ? ? ? ? ch[k++]='1'; continue; ? ? ? ? } ? ? ? ? if(a[i] > b[j]){ ? ? ? ? ? ? ch[k++]='0'; flag=0; continue; ? ? ? ? } ? ? ? ? if(a[i] < b[j]){ ? ? ? ? ? ? ch[k++]='0'; a[i-1]--; continue; ? ? ? ? } ? ? } ? ? int mark=0; ? ? for(int i=k-1;i>=0;i--) { ? ? ? ? if(!mark && ch[i]=='0') continue; ? ? ? ? s+=ch[i]; ? ? ? ? mark=1; ? ? } ? ? if(mark) ? ? ? ? for(vector<string>::size_type i=p;i<a.size();i++) ? ? ? ? ? ? s+=a[i]; ? ? else { ? ? ? ? int ans=0; ? ? ? ? for(vector<string>::size_type i=p;i<a.size();i++){ ? ? ? ? ? ? if(!ans && a[i]=='0') continue; ? ? ? ? ? ? ans=1; ? ? ? ? ? ? s+=a[i]; ? ? ? ? } ? ? } ? ? if(s.size()==0) return "0"; ? ? return s; } string fan(string a,string b){ ? ? if(a.size()<b.size()) return a; ? ? while(a.size()>=b.size()){ ? ? ? ? if(a==b) return "0"; ? ? ? ? if(judge(a,b)>0) ? ? ? ? ? ? a = fan1(a,b,b.size()-1,b.size()-1); ? ? ? ? else if(!judge(a,b)) ? ? ? ? ? ? a = fan1(a,b.size(),b.size()-1); ? ? ? ? else break; ? ? } ? ? return a; } string gcd(string a,string b){ ? ? return gcd(b,fan(a,b)); } int main(){ ? ? int n; ? ? cin>>n; ? ? for(int i=0;i<n;i++){ ? ? ? ? string a,b; ? ? ? ? cin>>a>>b; ? ? ? ? string c=gcd(a,b); ? ? ? ? cout<<"Case #"<<i+1<<": "; ? ? ? ? cout<<c<<endl; ? ? } }