BZOJ1876SDOI2009SuperGCD 高精度 更相减损法

更相减损法： gcd(a,b)=gcd(a/2,b/2)∗2 g c d ( a , b ) = g c d ( a / 2 , b / 2 ) ∗ 2 当a，b均为偶数
gcd(a,b)=gcd(a/2,b) g c d ( a , b ) = g c d ( a / 2 , b ) 当仅有a为偶数
gcd(a,b)=gcd(a,b/2) g c d ( a , b ) = g c d ( a , b / 2 ) 当仅有b为偶数
gcd(a,b)=gcd(max(a,b)−min(a,b),min(a,b)) g c d ( a , b ) = g c d ( m a x ( a , b ) − m i n ( a , b ) , m i n ( a , b ) ) 当其中一个参数为0时，另外一个参数即为答案

/************************************************************** Problem: 1876 User: YJMSTR Language: C++ Result: Accepted Time:1500 ms Memory:840 kb****************************************************************/#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define Max(_A,_B) (_A>_B?_A:_B)#define Min(_A,_B) (_A<_B?_A:_B)int read(){ int s = 0;bool f = 1;char c = getchar(); while(c > '9' || c < '0'){if(c == '-') f = 0; c = getchar();} while(c >= '0' && c <= '9') { s = s * 10 + c - '0'; c = getchar(); } return f == 1 ? s : -s;}typedef long long ll;const int base = 100000000, bit = 8, maxn = 1255;int n;char s[10007];struct bign{ int a[maxn], len; void sub(bign b) { //减b for (int i = 1; i <= 1200; i++) { if(i <= b.len) a[i] -= b.a[i]; if(a[i] < 0) { a[i] += base; a[i + 1]--; } } while(!a[len] && len) len--; } void div() {//自除2 for (int i = 1; i <= len; i++) { if(a[i]&1) a[i - 1] += base >> 1; //只有偶数情况才会用到div，所以不用考虑末位是奇数的情况 a[i] >>= 1; } while(!a[len]) len--; } void mul() { //自乘2 for (int i = len; i >= 1; i--) { a[i] <<= 1; a[i + 1] += a[i]/base, a[i] %= base; } while(a[len + 1]) len++; } void operator =(char *str) { int l = strlen(str + 1); len = l % bit ? l / bit + 1 : l / bit; for (int i = 1; i <= len; i++) { int s = Max(1, l - i * bit + 1); int t = l - (i - 1) * bit; for (int j = s; j <= t; j++) a[i] = a[i] * 10 + str[j] - '0'; } } void print() { while(!a[len]) len--; for (int i = len; i >= 1; i--) { if(i == len) printf("%d", a[i]); else printf("%08d", a[i]); } } bool operator>(bign b) { if(len < b.len) return false; if(len > b.len) return true; for (int i = len; i >= 1; i--) { if(a[i] > b.a[i]) return true; if(a[i] < b.a[i]) return false; } return true; }}a, b;int main() { // n = read(); scanf("%s", s+1); a = s; scanf("%s", s+1); b = s; int g = 0; for(;;){ if((a.a[1]&1)==0&&(b.a[1]&1)==0) { a.div(); b.div(); g++; }else if((a.a[1]&1)==0) a.div(); else if((b.a[1]&1)==0) b.div(); if(a > b){ a.sub(b); if(!a.len){ while(g--) b.mul(); b.print(); return 0; } }else{ b.sub(a); if(!b.len){ while(g--) a.mul(); a.print(); return 0; } } } return 0;}