传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1876
二进制gcd 学到了(' ' ) 高精还得压位，最开始没写压位，然后调了1h后又重写了一遍(' ' ) 怨念深重
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = 10010;
const int inf = 1000000000; struct bgint {
int n, a[maxn];
bgint() {
n = 0; memset(a, 0, sizeof(a));
}
bgint operator - (const bgint &x) const {
bgint ret; ret.n = max(x. n, this-> n);
for(int i = 1; i <= ret. n; ++ i) {
ret. a[i] += this-> a[i] - x. a[i];
if(ret. a[i] < 0) ret. a[i] += inf, ret. a[i + 1] --;
}
while(ret. a[ret. n] == 0 && ret. n != 1) ret. n --;
return ret;
}
}; bgint mov(const bgint &x) {
bgint ret; ret. n = x. n;
for(int i = 1; i <= ret. n; ++ i) {
ret. a[i] += x. a[i] * 2;
ret. a[i + 1] += ret. a[i] / inf;
ret. a[i] %= inf;
}
if(ret. a[ret. n + 1]) ret. n ++;
return ret;
} bgint div(const bgint &x) {
bgint ret;
if(x. a[x.n] < 2) {
ret. n = x. n - 1;
for(int i = 1; i <= ret. n; ++ i) ret. a[i] = x. a[i];
ret. a[ret. n] += x. a[x.n] * inf;
for(int i = ret. n; i >= 1; -- i) ret. a[i - 1] += ret. a[i] % 2 * inf, ret. a[i] /= 2;
ret. a[0] = 0;
}
else {
ret. n = x.n;
for(int i = 1; i <= ret. n; ++ i) ret. a[i] = x. a[i];
for(int i = ret. n; i >= 1; -- i) ret. a[i - 1] += ret. a[i] % 2 * inf, ret. a[i] /= 2;
ret. a[0] = 0;
}
return ret;
} bool even (const bgint &x) {
return (x. a[1] & 1);
} bool is (const bgint &x, const bgint &t) {
if(x. n != t. n) return 0;
for(int i = 1; i <= x. n; ++ i) if(x. a[i] != t. a[i]) return 0;
return 1;
} bool com(const bgint &x, const bgint &t) {
if(x. n > t. n) return 0;
else if(x. n < t. n) return 1;
for(int i = x. n; i >= 1; -- i) {
if(x. a[i] > t. a[i]) return 0;
else if(x. a[i] < t.a[i]) return 1;
}
return 0;
} void print(const bgint &x) {
for(int i = x. n; i >= 1; -- i) {
if(i == x.n ) printf("%d", x. a[i]);
else printf("%09d", x. a[i]);
}
} bgint gcd(bgint a, bgint b) {
bgint ret; ret. a[1] = 1, ret. n = 1;
int cnt = 0;
while(!is(a, b)) {
if(even(a)) {
if(even(b)) {
if(!com(a, b)) a = div((a - b));
else b = div((b - a));
}
else b = div(b);
}
else {
if(even(b)) a = div(a);
else b = div(b), a = div(a), cnt ++;
}
// ++ x; print(a); cout << " "; print(b); cout << endl;
}
for(int i = 1; i <= cnt; ++ i) a = mov(a);
return a;
} char s[maxn]; bgint read() {
scanf("%s", s + 1);
bgint ret; ret. n = (int)strlen(s + 1); ret. n = ret. n % 9 == 0 ? ret. n / 9 : ret. n / 9 + 1;
int sl = (int)strlen(s + 1);
for(int i = 1; i <= ret. n; ++ i) {
int t = 1;
for(int j = (i - 1) * 9 + 1; j <= min(i * 9, sl); ++ j)
ret. a[i] += (int)(s[sl - j + 1] - '0') * t, t *= 10;
}
return ret;
} void sov() {
bgint x = read(), t = read();
print(gcd(x, t));
} int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
sov();
return 0;
}