《P2152 [SDOI2009] SuperGCD》
题目描述
Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天 Sheng bill 很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。
输入格式
共两行，第一行一个整数 a，第二行一个整数 b。
输出格式
一行，表示 a 和 b 的最大公约数。
输入输出样例
输入 #1复制
12 54
输出 #1复制
6
说明/提示
数据规模与约定
- 对于 20% 的数据，有 0<a,b≤1018。
- 对于 100% 的数据，有 0<a,b≤1010000。
代码实现：
#include <bits/stdc++.h> using namespace std; const long long MOD = 10000000000000000ll; const int MAXN = 700; long long A[MAXN], B[MAXN]; char buf[MAXN << 4]; inline long long str2ll(char s[], int l, int r) { long long res = 0, pow10 = 1; for (int i = l; i <= r; i++) res += (s[i] ^ 48) * pow10, pow10 *= 10ll; return res; } inline void read_big(long long x[]) { scanf("%s", buf + 1); int len = x[0] = strlen(buf + 1); x[0] = (len + 15) >> 4; for (int i = 1; i <= (len >> 1); i++) swap(buf[i], buf[len - i + 1]); // 修复：将i的定义移到for循环外，扩大作用域 int i; for (i = 1; i + 15 <= len; i += 16) x[(i + 15) >> 4] = str2ll(buf, i, i + 15); if (i <= len) x[x[0]] = str2ll(buf, i, len); } inline void print_big(long long x[]) { printf("%lld", x[x[0]]); for (int i = x[0] - 1; i >= 1; i--) printf("%016lld", x[i]); } inline void cp(long long a[], long long b[]) { memcpy(b, a, MAXN << 3); } inline void clr(long long x[]) { memset(x, 0, MAXN << 3); } inline bool is_even(long long x[]) { return !(x[1] & 1); } inline void div2(long long x[]) { bool rem[MAXN] = {0}; if (!x[0]) return; for (int i = x[0]; i; i--) rem[i - 1] = x[i] & 1, x[i] >>= 1; for (int i = x[0]; i; i--) if (rem[i]) x[i] += MOD >> 1; while (x[0] && !x[x[0]]) --x[0]; } inline void mul2(long long x[]) { long long carry = 0; for (int i = 1; i <= x[0] + 1; i++) { x[i] = (x[i] << 1) + carry; carry = x[i] / MOD; x[i] %= MOD; } while (x[x[0] + 1]) ++x[0]; } inline int cmp(long long a[], long long b[]) { if (a[0] > b[0]) return 1; if (a[0] < b[0]) return -1; for (int i = a[0]; i; i--) { if (a[i] > b[i]) return 1; if (b[i] > a[i]) return -1; } return 0; } inline void sub(long long a[], long long b[], long long res[]) { clr(res); for (int i = 1; i <= a[0]; i++) { res[i] += a[i] - b[i]; if (res[i] < 0) res[i] += MOD, --res[i + 1]; } res[0] = a[0]; while (res[0] && !res[res[0]]) --res[0]; } long long tmp[MAXN], res[MAXN]; inline void big_gcd(long long a[], long long b[]) { clr(res); if (cmp(a, b) == -1) cp(a, tmp), cp(b, a), cp(tmp, b); bool a_even, b_even; int cnt2 = 0; while (b[0]) { a_even = is_even(a); b_even = is_even(b); if (a_even && b_even) { cnt2++; div2(a); div2(b); } else if (!a_even && b_even) { div2(b); } else if (a_even && !b_even) { div2(a); } else { sub(a, b, tmp); cp(tmp, a); } if (cmp(a, b) == -1) cp(a, tmp), cp(b, a), cp(tmp, b); } cp(a, res); while (cnt2--) mul2(res); } int main() { read_big(A); read_big(B); big_gcd(A, B); print_big(res); return 0; }