[SDOI2009]SuperGCD

毒瘤。
有个叫Stein算法的东西可以优化更相减损数，大概流程是
如果有一个是1,那么gcd一定是1。
如果两个中有一个偶数，这个偶数因子对答案没有任何贡献，可以直接除了。
如果两个中两个都是偶数，那么就可以给gcd直接乘2
然后就过了。
成就感++

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char tp[10005];
struct Big{
	int s[10005];int len;
	Big(){memset(s,0,sizeof s);len=0;}
	void input() {
		scanf("%s",tp);
		len=strlen(tp);
		for(int i=0;i<len/2;i++) swap(tp[i],tp[len-i-1]);
		for(int i=0;i<len;i++) s[i]=tp[i]-'0';
	}
	Big operator - (const Big &rhs) const {
		Big ans;
		ans.len=max(len,rhs.len);
		int jian=0,cnt=0;
		for(int i=0;i<ans.len;i++) {
			ans.s[i]=s[i]-rhs.s[i]-jian;
			while(ans.s[i]<0) ans.s[i]+=10,cnt++;
			jian=cnt;
			cnt=0;
		}
		while(ans.s[ans.len-1]==0&&ans.len) ans.len--;
		return ans;
	}
	bool operator < (const Big &rhs) const {
		if(len>rhs.len) return 0;
		else if(len<rhs.len) return 1;
		for(int i=len-1;~i;i--) 
                      if(s[i]<rhs.s[i])return 1;
                      else if(s[i]>rhs.s[i]) return 0;
		return 0;
	}
	void print() {
		for(int i=len-1;~i;i--) printf("%d",s[i]);
		putchar(' ');
	}
	void div() {
		int tui=0;
		for(int i=len-1;~i;i--) {
			s[i]+=tui;
			tui=(s[i]&1)*10;
			s[i]>>=1;
		}
		if(s[len-1]==0&&len>1) len--;
	}
	void mul() {
		int jin=0;
		for(int i=0;i<len;i++) {
			s[i]=(s[i])<<1;
			s[i]+=jin;
			jin=(s[i]/10);
			s[i]%=10;
		}
		while(jin) s[len++]=jin%10,jin/=10;
	}
	bool operator != (const Big &rhs) const {
		if(len!=rhs.len) return 1;
		for(int i=0;i<len;i++) if(s[i]!=rhs.s[i]) return 1;
		return 0;
	} 
}A,B;
int cnt=0;
void get() {
	while(A!=B){
		if(A<B) swap(A,B);
		if((A.s[0]&1)&&(!(B.s[0]&1))) {while(!(B.s[0]&1))B.div();}
		if((!(A.s[0]&1))&&(B.s[0]&1)) {while(!(A.s[0]&1))A.div();continue;}
		if(B.len==1&&B.s[0]==1) {A=B;return;}
		while((!(A.s[0]&1))&&(!(B.s[0]&1))) A.div(),B.div(),cnt++;
		A=A-B;
	}
}
int main() {
	A.input();B.input();
	get();
	for(int i=1;i<=cnt;i++) A.mul();
	A.print();
	return 0;
}