题解 P2152 【[SDOI2009]SuperGCD】
不知道提交了几次才AC。。。 写的时候出现了很多问题，本题解目的是说一下我从疯狂WA到AC过程出现的一些问题。
首先是高精。 不用高精只有20分，高精中要注意的问题： 1、乘法高精
big mul(big a) {
int in = 0;
FOR(i,0,a.len-1) {
a.num[i] = a.num[i] * 2 + in;
in = 0;
if(a.num[i] >= 10) {
in = a.num[i] / 10;
a.num[i] %= 10;
if(i == a.len - 1) a.len ++;
}
}
return a;
}这里面的变量in是用来进位的，但是要注意，变量in在使用完应该先清零，否则会WA 6个点。 不要问我怎么知道的
2、减法高精
big operator -(const big &a) {
big c;
c.clean();
c.len = max(a.len,len);
FOR(i,0,c.len-1) {
c.num[i] += (num[i] - a.num[i]);
if(c.num[i] < 0) {
c.num[i] += 10;
c.num[i+1] --;
}
}
while(c.num[c.len-1] == 0) c.len --;
return c;
}这里我重载了‘ - ’运算符，但要注意减法的退位问题。我这里的退位没有用变量标记，而是直接对变量c的相应位处理，所以这里的
c.num[i] += (num[i] - a.num[i]);应为 += 而不是 = ，这样就要求变量c在计算前应初始化。 附上初始化函数。
void clean() {
memset(num,0,sizeof(num));
len = 0;
}其次要说一下题解中的一个误区。我发现有的题解中说到：如果a是偶数同时b也是偶数，那么gcd(a,b) = gcd(a/2,b/2); 这样是错误的。正确的应该是*gcd(a,b) = 2 gcd(a/2,b/2);**
而且，我一开始写的是递归程序，但是不知道原因蜜汁RE了10个点，所以建议本题写递推。递推使用的是更相减损术，注意在做减法时应先判断被减数和减数的大小关系，一定要大减小。
附上判断大小的代码
bool operator <(const big &a) {
if(len != a.len) return len < a.len;
FOR2(i,len-1,0)
if(num[i] != a.num[i]) return num[i] < a.num[i];
return false;
}
bool operator ==(const big &a) {
if(len != a.len) return false;
FOR2(i,len-1,0)
if(num[i] != a.num[i]) return false;
return true;
}除此之外提示一下，c++自带的swap函数可以swap任意类型变量。
最后附上AC代码 （丑勿喷）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOR2(i,a,b) for(int i=a;i>=b;i--)
#define LL long long int
using namespace std;
const int maxn = 2e4 + 7;
struct big {
int num[maxn],len;
void clean() {
memset(num,0,sizeof(num));
len = 0;
}
big operator -(const big &a) {
big c;
c.clean();
c.len = max(a.len,len);
FOR(i,0,c.len-1) {
c.num[i] += (num[i] - a.num[i]);
if(c.num[i] < 0) {
c.num[i] += 10;
c.num[i+1] --;
}
}
while(c.num[c.len-1] == 0) c.len --;
return c;
}
bool operator <(const big &a) {
if(len != a.len) return len < a.len;
FOR2(i,len-1,0)
if(num[i] != a.num[i]) return num[i] < a.num[i];
return false;
}
bool operator ==(const big &a) {
if(len != a.len) return false;
FOR2(i,len-1,0)
if(num[i] != a.num[i]) return false;
return true;
}
};
bool check(big a) { //判断是不是偶数
int x = a.num[0];
return (x == 0) || (x == 2) || (x == 4) || (x == 6) || (x == 8);
}
big chu(big a) { //除以2的运算函数
FOR2(i,a.len-1,1) {
a.num[i-1] += (a.num[i] % 2) * 10;
a.num[i] /= 2;
}
a.num[0] /= 2;
while(a.num[a.len - 1] == 0) a.len --;
return a;
}
big mul(big a) { //乘2的运算函数
int in = 0;
FOR(i,0,a.len-1) {
a.num[i] = a.num[i] * 2 + in;
in = 0;
if(a.num[i] >= 10) {
in = a.num[i] / 10;
a.num[i] %= 10;
if(i == a.len - 1) a.len ++;
}
}
return a;
}
int main() {
bool ca,cb;
big a,b;
int cnt = 0;
char ch[maxn];
scanf("%s",ch);
a.len = strlen(ch);
FOR2(i,a.len-1,0) a.num[i] = ch[a.len - i - 1] - '0';
scanf("%s",ch);
b.len = strlen(ch);
FOR2(i,b.len-1,0) b.num[i] = ch[b.len - i - 1] - '0';
while(!(a == b)) { //由于没有重载 != 运算符，只重载了 == ，所以只能这样判断
if(a < b) swap(a,b);
ca = check(a); cb = check(b);
if(ca && cb) {
a = chu(a);
b = chu(b);
cnt ++;
}
else if(cb) b = chu(b);
else if(ca) a = chu(a);
else a = a - b;
}
FOR(i,1,cnt) a = mul(a);
FOR2(i,a.len-1,0) printf("%d",a.num[i]);
return 0; //华丽的 return 0;
}