rt

题目：https://loj.ac/p/10208

最后三个点 TLE。

//P2152
#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
struct BigInteger{ int n, a[N]; } o, p;

BigInteger read(){
	BigInteger ans; int k = 0; char ch = getchar();
	memset(ans.a, 0, sizeof(ans.a)); 
	while(ch >= '0' && ch <= '9') ans.a[++k] = ch - '0', ch = getchar();
	reverse(ans.a + 1, ans.a + k + 1);
	ans.n = k;
	return ans;
}
void print(BigInteger x, int k){
	for(int i = x.n; i; -- i) printf("%d", x.a[i]);
	if(k) puts(""); else putchar(' ');
}

bool judge(BigInteger x, BigInteger y){
	if(x.n != y.n) return x.n < y.n;
	for(int i = x.n; i; -- i) if(x.a[i] != y.a[i]) return x.a[i] < y.a[i];
	return false;
}
bool equal(BigInteger x, BigInteger y){
	if(x.n != y.n) return false;
	for(int i = 1; i <= x.n; ++ i) if(x.a[i] != y.a[i]) return false;
	return true;
}
void sub(BigInteger &x, BigInteger y){
	for(int i = 1; i <= y.n + 1; ++ i){
		if(x.a[i] < y.a[i]) -- x.a[i+1], x.a[i] += 10;
		x.a[i] -= y.a[i];
	}
	while(x.a[x.n] == 0) -- x.n;
}
void div2(BigInteger &x){
	for(int i = x.n; i; -- i){
		if(x.a[i] & 1) x.a[i-1] += 10;
		x.a[i] /= 2;
	}
	while(x.a[x.n] == 0) -- x.n;
}
void mul2(BigInteger &x){
	for(int i = 1; i <= x.n; ++ i) x.a[i] *= 2;
	for(int i = 1; i <= x.n; ++ i) 
		if(x.a[i] >= 10) x.a[i] -= 10, ++ x.a[i+1];
	while(x.a[x.n+1]) ++ x.n;
}

BigInteger gcd(BigInteger x, BigInteger y){
	int cnt = 0;
	while(!equal(x, y)){
		if(judge(x, y)) swap(x, y);
		if(y.n == 1 && y.a[1] == 1) break;
		bool a = x.a[1] & 1, b = y.a[1] & 1;
		if(a && b) sub(x, y);
		else if(!a && b) div2(x);
		else if(a && !b) div2(y);
		else if(!a && !b) div2(x), div2(y), ++ cnt;
	}
	while(cnt --) mul2(y);
	return y;
}

int main(){
//	freopen("gcd7.in", "r", stdin);
//	freopen("gcd7.out", "w", stdout);
	o = read(), p = read();
	print(gcd(o, p), 1);
	return 0;
}