You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 256 MB

题目描述

对于最大公约数，有一种出自《九章算术》的更相减损术。

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

即：（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

今天将带大家实现更相减损术。

具体流程如下：

1. 令 $p=1$；
2. 若 $a$ 和 $b$ 不都是偶数，则转 (5)；
3. 令 $p=p\times 2,a=a/2,b=b/2$；
4. 转 (2)；
5. 令 $t=|a-b|$；
6. 若 $t=0$，则返回并输出 $a\times p$；
7. 若 $t$ 为奇数，则转 (10)；
8. 令 $t=t/2$；
9. 转 (7)；
10. 若 $a\ge b$，则令 $a=t$；否则，令 $b=t$；
11. 转 (5)。

请你以此流程进行实现。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 bigint.h。

BigInteger gcd(BigInteger a, BigInteger b)，传入两个高精度整数 $a$ 和 $b$，返回其最大公约数。

BigInteger 是我们定义的一个非负整数高精度类，提供以下可以使用的接口：

struct BigInteger
{
    void operator=(const BigInteger& o);
    bool is_odd();
    bool is_zero();
    bool operator==(const BigInteger& o);
    bool operator!=(const BigInteger& o);
    bool operator<(const BigInteger& o);
    bool operator>(const BigInteger& o);
    bool operator<=(const BigInteger& o);
    bool operator>=(const BigInteger& o);
    BigInteger operator-(const BigInteger& o);
    BigInteger& operator-=(const BigInteger& o);
    BigInteger operator>>(int x);
    BigInteger& operator>>=(int x);
    BigInteger operator<<(int x);
    BigInteger& operator<<=(int x);
};

具体来说，我们的非负大整数类支持和 C++ 的一般非负整数一样的判断大小（是否相等、大于、小于、等于等）、二进制左移右移功能，以及减法功能。

需要注意的是：我们的减法 $a-b$ 仅当 $a\ge b$ 时才能正确运行，我们的程序会先判断传入的两个数是否满足条件，不满足则会让程序直接返回 Runtime Error。

此外还有对象可直接调用的两个 bool 函数接口：

• is_odd：判断当前非负整数的奇偶性。是奇数则返回 true，偶数则返回 false。
• is_zero：判断当前非负整数是否等于 $0$。是则返回 true，不是则返回 false。

你无需考虑上述重载运算符和函数接口运行的时间复杂度，只需要正确调用他们，并返回正确的结果即可。

以下我们给出一个代码提交实例（会固定返回答案 $\lfloor a/2 \rfloor$，仅作为示例，不保证能得分）：

#include "bigint.h"
BigInteger gcd(BigInteger a, BigInteger b)
{
    return a >> 1;  
}

因为在非负整数下，右移一位等价于除以 $2$（向下整除）。

你不需要，也不应该，实现主函数。

我们给出一个样例，在本地调试时，你可以直接使用 int 调试。

54
12

6

子任务

• 子任务 1（80 分）：保证 $1\le a,b\le 10^{1000}$；
• 子任务 2（20 分）：保证 $1\le a,b\le 10^{10000}$。

提示

Chap 01 绪论，更相减损术，习题 [1-25]。

上述的更相减损术相比于通用的辗转相除法，仍旧缺少两种需要处理的退化情况：

• $a=0$ 或者 $b=0$ 时，返回结果为 $b$ 或者 $a$；
• 当 $a<0$ 或者 $b<0$ 时，需要先取绝对值，再进行最大公约数的运算，保证返回结果是非负的。

本题给定的数据范围不需要你考虑这些退化情况。但是如果想在其他的数论函数中使用，则必须考虑这些才能正确实现对应功能。