题目传送门(BZOJ)
>原文链接<

题解 :

高精度GCD模板

平时使用的辗转相除, 由于高精度取模太慢了, 到这里并不适用, 我们采用复杂度一样的更相减损法

更相减损的步骤 :

  • 判断两个数是否都是2的倍数, 如果是, 累加(乘)一个2到答案里, 两数同时约2
  • 有一个数是2的倍数 : 只把它约2
  • 用大数减小数, 与原来的小数构成新的两个数, 重复以上过程
  • 发现除以2的次数要比相减的次数多, 复杂度有保证

这样最后得到的一个非0数, 与之前累乘的2再乘一次, 就是最后的答案.

我们只需要实现高精度乘2, 高精度除以2, 高精度减法, 高精度比较大小即可.

注意效率问题, 要压位, 用long long压16位或者int压8位都行, 前者应该快一点? 不过都能过

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>const int p = 1e8; struct INT { char w[15100]; int a[5000], len; INT(){memset(a, 0, sizeof a); len = 0;} inline int& operator [] (const int cur) {return a[cur];} inline const int& operator [] (const int cur) const {return a[cur];} inline bool operator < (const INT &b) const { if(len != b.len) return len < b.len; for(int i = len; i >= 1; i -- ) if(a[i] != b[i]) return a[i] < b[i]; return false; } inline void operator -= (const INT &b) { for(int i = 1; i <= len; i ++ ) { a[i] -= b[i]; if(a[i] < 0) a[i]+=p, a[i+1] --; } for(; len && !a[len]; len -- ); } inline void operator *= (const int &x) { for(int i = len; i >= 1; i -- ) { a[i] <<= 1; if(a[i] >= p) a[i+1] += a[i]/p, a[i]-=p; } if(a[len+1]) ++ len; } inline void operator /= (const int &x) { for(int i = len; i >= 1; i -- ) { if(a[i]&1) a[i-1]+=p; a[i] >>= 1; } for(; len && !a[len]; len -- ); } inline bool is0() {return len == 0;} inline bool is2() {return a[1] & 1;} inline void read() { scanf("%s", w+1); int l = strlen(w+1); std :: reverse(w+1, w+l+1); int now = 0, f = 1; for(int i = 1; i <= l; i ++ ) { now += f*(w[i]^48); if(i%8 == 0) a[++len] = now, now /= p, f = 1; else f *= 10; } if(now) a[++len] = now; for(; len && !a[len]; len -- ); } inline void print() { printf("%d", a[len]); for(int i = len-1; i >= 1; i -- ) printf("%08d", a[i]); putchar('\n'); } inline void gcd(INT &b) { int f = 0; while(!is0()&&!b.is0()) { while(!is2() &&!b.is2()) ++ f, *this /= 2, b /= 2; while(!is2() ) *this /= 2; while(!b.is2()) b /= 2; if(b < *this) std :: swap(b, *this); b -= *this; } if(is0()) *this = b; while(f -- ) *this *= 2; }}a, b;int main() { a.read(), b.read(); a.gcd(b); a.print();}