提交记录

#include<bits/stdc++.h>
using namespace std;
struct Bignum{
	int size,a[1252];
	void init(){
		size=0;
		memset(a,0,sizeof(a));
	}
	int getsize(int x){
		while (!a[x]&&x>=0) x--;
		return size=x+1;
	} 
	void read(){
		init(); string s; cin>>s;
		for (int i=s.size()-1,k=1;i>=0;i--){
			a[size]+=(s[i]-'0')*k,k*=10;
			if (k==100000000) k=1,size++;
		}
		getsize(size+2);
	}
	void print(){
		if (size==0){ printf("0\n"); return; }
		printf("%d",a[size-1]);
		for (int i=size-2;i>=0;i--) printf("%08d",a[i]);
		printf("\n");
	}
	bool operator<(const Bignum& other)const{
		if (size<other.size) return 1;
		if (size>other.size) return 0;
		for (int i=size-1;i>=0;i--){ 
			if (a[i]<other.a[i]) return 1;
			if (a[i]>other.a[i]) return 0;
		}
		return 0;
	}
	bool operator==(const Bignum& other)const{
		if (size!=other.size) return 0;
		for (int i=size-1;i>=0;i--) if (a[i]!=other.a[i]) return 0;
		return 1;
	}
	Bignum operator-(const Bignum other){
		Bignum s; s.init();
		for (int i=0;i<size;i++){
			if (a[i]<other.a[i]) a[i]+=1e8,a[i+1]--;
			s.a[i]=a[i]-other.a[i];
		}
		s.getsize(size); return s;
	}
	Bignum Divtwo(){
		for (int i=size-1;i>=0;i--){
			if (a[i]&1) a[i]--,a[i-1]+=1e8;
			a[i]>>=1;
		}
		getsize(size); return *this;
	}
	Bignum Multwo(){
		for (int i=0;i<size;i++){
			a[i]<<=1;
			if (a[i]>=1e8) a[i]-=1e8,a[i+1]++;
		}
		getsize(size+2); return *this;
	}
};
Bignum gcd(Bignum x,Bignum y){
	Bignum final; int cnt=0;
	while (1){
		if (y==x){ final=y; break; }
		if (y<x) swap(x,y);
		if (!x.size){ final=y; break; }
		if (!y.size){ final=x; break; }
		if ((x.a[0]&1)&&!(y.a[0]&1)) y.Divtwo();
		if ((y.a[0]&1)&&!(x.a[0]&1)) x.Divtwo();
		if (!(x.a[0]&1)&&!(y.a[0]&1)) x.Divtwo(),y.Divtwo(),cnt++;
		if ((x.a[0]&1)&&(y.a[0]&1)){ Bignum tmp=y; y=x; x=tmp-x; }
	}
	while (cnt--) final.Multwo();
	return final;
}
signed main(){
	Bignum a,b;
	a.read(),b.read();
	gcd(a,b).print();
	return 0;
}