BZOJ 1876: [SDOI2009]SuperGCD

1876: [SDOI2009]SuperGCD

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 3060 Solved: 1036
[Submit][Status][Discuss]

Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。

Input

共两行：第一行：一个数A。第二行：一个数B。

Output

一行，表示A和B的最大公约数。

Sample Input

12
54

Sample Output

HINT

对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。

Source

Day1

[Submit][Status][Discuss]

首先普通的GCD显然是不行的，而高精度又难以进行mod运算（至少我不会写），所以我们需要一个神奇的求最大公约数的方法。

好像是在60年代，某位前辈深感欧几里得算法求GCD的不便，对其进行了改进，适合大整数（大素数）的GCD过程，而且易于理解。

首先，我们需要了解以下知识：

　　1. GCD(a, b) = k * GCD(a / k, b / k) 其中，k是a和b的一个公因数。

　　2. GCD(a, b) = GCD(a / k, b) 其中，k仅为a的因数，而非b的因数。

　　3. GCD(a, b) = GCD(a - b, b) 其中，a大于等于b。

对于知识1和2，当k=2的时候，有：

如果a,b都是偶数，则GCD(a, b) = 2 * GCD(a / 2, b / 2)。

如果a,b中只有一个偶数，则GCD(a, b) = GCD(a / 2, b)。（假设a是偶数）

而*2和/2的运算可以通过位运算快速实现（当然，不这么做也是可以过的）。

  1 #include <bits/stdc++.h>
  2 
  3 const int siz = 1500;
  4 const int mod = 100000000;
  5 
  6 struct Int
  7 {
  8     int num[siz], len;
  9     
 10     inline Int(void) {
 11         memset(num, 0, sizeof(num)), len = 1;
 12     }
 13     
 14     inline Int(char *s) {
 15         int l = strlen(s);
 16         len = (l + 7) >> 3;
 17         memset(num, 0, sizeof(num));
 18         for (int i = 0; i < l; ++i)
 19             (num[(l - i + 7) >> 3] *= 10) += s[i] - 48;
 20     }
 21     
 22     inline friend bool operator < (const Int &a, const Int &b) {
 23         if (a.len != b.len)
 24             return a.len < b.len;
 25         for (int i = a.len; i; --i)
 26             if (a.num[i] != b.num[i])
 27                 return a.num[i] < b.num[i];
 28         return false;
 29     }
 30     
 31     inline void sub(const Int &a) {
 32         for (int i = 1; i <= a.len; ++i)
 33             num[i] -= a.num[i];
 34         for (int i = 1; i <= len; ++i)
 35             if (num[i] < 0) 
 36                 num[i] += mod, --num[i + 1];
 37         while (len > 1 && !num[len])--len;
 38     }
 39     
 40     inline void mul2(void) {
 41         for (int i = 1; i <= len; ++i)
 42             num[i] <<= 1;
 43         for (int i = 1; i <= len; ++i)
 44             if (num[i] >= mod)
 45                 num[i] -= mod, ++num[i + 1];
 46         while (num[len + 1])++len;
 47     }
 48     
 49     inline void div2(void) {
 50         for (int i = len; i; --i) {
 51             if (i > 1 && (num[i] & 1))
 52                 num[i - 1] += mod;
 53             num[i] >>= 1;
 54         }
 55         while (len > 1 && !num[len])--len;
 56     }
 57     
 58     inline bool even(void) {
 59         return !(num[1] & 1);
 60     }
 61     
 62     inline bool zero(void) {
 63         return len == 1 && !num[1];
 64     }
 65     
 66     inline void print(void) {
 67         printf("%d", num[len]);
 68         for (int i = len - 1; i; --i)
 69             printf("%08d", num[i]);
 70         putchar('
');
 71     }
 72 };
 73 
 74 inline Int gcd(Int a, Int b)
 75 {
 76     int bit = 0;
 77     while (true)
 78     {
 79         if (a.zero()) {
 80             while (bit--)b.mul2();
 81             return b;
 82         }
 83         if (b.zero()) {
 84             while (bit--)a.mul2();
 85             return a;
 86         }
 87         int flag = 0;
 88         if (a.even())++flag, a.div2();
 89         if (b.even())++flag, b.div2();
 90         if (flag == 2)
 91             ++bit;
 92         else {
 93             if (a < b)
 94                 b.sub(a);
 95             else
 96                 a.sub(b);
 97         }
 98     }
 99 }
100 
101 char a[10005];
102 char b[10005];
103 
104 signed main(void)
105 {
106     scanf("%s", a);
107     scanf("%s", b);
108     gcd(Int(a), Int(b)).print();
109 }

@Author: YouSiki