洛谷 P2152 [SDOI2009] SuperGCD

// P2152 第 ① 版：题面 20% 那一档（a, b ≤ 10¹⁸）—— 直接套第 40 章正文那份欧几里得
//
// ★ 题面自己把这一档写好了：「对于 20% 的数据，0 < a, b ≤ 10¹⁸」
//   ⇒ `unsigned long long` 装得下（上限 1.8 × 10¹⁹），一行 while 就完事 ⇒ **稳拿 20 分**。
//
// ⚠ 而 100% 那一档是 **10¹⁰⁰⁰⁰**（一万位）——
//   任何内置整数类型都装不下，只能写高精度（见 p2152.cpp）。
//
// ⚠ 这一版在大数据上会读进一个截断的值，答案自然是错的 —— 它只负责那 20 分。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string sa, sb;
    if (!(cin >> sa >> sb)) return 0;
    // ⚠ 超过 19 位就装不下了：这一版只对 20% 那一档负责
    unsigned long long a = 0, b = 0;
    for (char c : sa) a = a * 10 + (unsigned)(c - '0');
    for (char c : sb) b = b * 10 + (unsigned)(c - '0');
    while (b) { unsigned long long t = a % b; a = b; b = t; }
    cout << a << '\n';
    return 0;
}

// P2152 正解 —— 压位高精度 ＋ 二进制 gcd（Stein 算法）
//
// ============ ★★★ 为什么不能照搬第 40 章那份欧几里得 ============
//
//   `gcd(a, b) = gcd(b, a mod b)` 里的那个 **mod，在高精度下是一次长除法** ——
//   一万位除以一万位，写起来长、跑起来更贵。
//   ⇒ 换成**只用「减法、判奇偶、除以 2」**的二进制 gcd：
//
//     · a、b 都是偶数 ⇒ gcd = 2 · gcd(a/2, b/2)      （公共的 2 先提出来记账）
//     · a 偶 b 奇     ⇒ gcd(a, b) = gcd(a/2, b)       （2 不是公因子，扔掉）
//     · a、b 都是奇数 ⇒ gcd(a, b) = gcd(|a−b|, min)   （更相减损，而差必是偶数）
//
//   ★★ 而[第 40 章第 9 步](/ch/40-gcd-euclid/)那条「每两步至少减半」的界，
//     在这里换了个形式又出现了一次：**每一轮至少有一个数被除以 2**
//     ⇒ 总轮数 O(log a + log b) ≈ 一万位 × 3.32 ≈ **11 万轮**，每轮 O(位数)。
//
// ============ 高精度怎么存 ============
//
//   压位：每个 uint32 存 8 位十进制（基数 10⁸），一万位 ⇒ 1250 个 limb。
//   要的操作只有四个：比较、减法、除以 2、乘以 2 —— **没有除法，也没有乘法**。
//
// ⚠ 「除以 2」要从高位往低位扫（借位往下带），「乘以 2」要从低位往高位扫（进位往上带）。

#include <bits/stdc++.h>
using namespace std;

static const unsigned BASE = 100000000u;         // 10⁸
static const int W = 8;

struct Big {
    vector<unsigned> d;                          // 低位在前
    void trim() { while (d.size() > 1 && d.back() == 0) d.pop_back(); }
    bool isZero() const { return d.size() == 1 && d[0] == 0; }
    bool isEven() const { return (d[0] & 1u) == 0; }
};

static Big fromString(const string& s) {
    Big r;
    for (int i = (int)s.size(); i > 0; i -= W) {
        int l = max(0, i - W);
        r.d.push_back((unsigned)stoul(s.substr(l, i - l)));
    }
    if (r.d.empty()) r.d.push_back(0);
    r.trim();
    return r;
}
static string toString(const Big& a) {
    string s = to_string(a.d.back());
    for (int i = (int)a.d.size() - 2; i >= 0; i--) {
        string t = to_string(a.d[i]);
        s += string(W - t.size(), '0') + t;
    }
    return s;
}
/** a 和 b 比大小：>0 / 0 / <0 */
static int cmp(const Big& a, const Big& b) {
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1;
    for (int i = (int)a.d.size() - 1; i >= 0; i--)
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
    return 0;
}
/** a -= b（要求 a ≥ b） */
static void sub(Big& a, const Big& b) {
    long long borrow = 0;
    for (size_t i = 0; i < a.d.size(); i++) {
        long long cur = (long long)a.d[i] - borrow - (i < b.d.size() ? (long long)b.d[i] : 0);
        if (cur < 0) { cur += BASE; borrow = 1; } else borrow = 0;
        a.d[i] = (unsigned)cur;
    }
    a.trim();
}
/** a /= 2 —— 从高位往低位，借位往下带 */
static void halve(Big& a) {
    unsigned rem = 0;
    for (int i = (int)a.d.size() - 1; i >= 0; i--) {
        unsigned long long cur = (unsigned long long)rem * BASE + a.d[i];
        a.d[i] = (unsigned)(cur >> 1);
        rem = (unsigned)(cur & 1ull);
    }
    a.trim();
}
/** a *= 2 —— 从低位往高位，进位往上带 */
static void twice(Big& a) {
    unsigned carry = 0;
    for (size_t i = 0; i < a.d.size(); i++) {
        unsigned long long cur = (unsigned long long)a.d[i] * 2 + carry;
        a.d[i] = (unsigned)(cur % BASE);
        carry = (unsigned)(cur / BASE);
    }
    if (carry) a.d.push_back(carry);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string sa, sb;
    if (!(cin >> sa >> sb)) return 0;
    Big a = fromString(sa), b = fromString(sb);

    long long shift = 0;
    while (a.isEven() && b.isEven()) { halve(a); halve(b); shift++; }   // 公共的 2 记账

    while (!a.isZero()) {
        while (a.isEven()) halve(a);              // a 的 2 不是公因子，扔掉
        while (b.isEven()) halve(b);
        if (cmp(a, b) >= 0) sub(a, b); else sub(b, a);   // 两个奇数相减，差必偶
    }
    while (shift--) twice(b);                     // 把记的账还回去

    cout << toString(b) << '\n';
    return 0;
}

// P2152 的生成器：./p2152Gen 种子 [档位]
//
// ★ 每个版本靠什么现形：
//   · p2152Small（用 unsigned long long 读）→ 只要**数超过 19 位**就完了。
//     ⇒ 档 0（20 位以内）是精确的 0，档 1 起必错。
//   · p2152Sub（更相减损，不提取因子 2）→ 它**答案永远是对的**，坏的只有复杂度
//     ⇒ [对拍原理上抓不到它](/sol/p3378/)，只能数步数 / 看秒表（见 p2152Count.cpp）。
//
// 档位：
//   0  ★ 题面 20% 那一档：a、b ≤ 10¹⁸（能和 p2152Small 对拍）
//   1  中等：约 200 位
//   2  ★ 顶格：约 10000 位（题面 100% 那一档）
//   3  ⚠⚠ **专门卡「不提因子 2」那一版**：a 和 b 差得很小（b = a − 小量）
//      ⇒ 更相减损每次只减掉一点点，而二进制 gcd 照样每轮减半
//   4  ★ 两个数含大量公共的 2（都乘上 2^k）—— 逼出「先把公共的 2 提出来」那一步
//
// ⚠ 题面 0 < a, b ⇒ 不能造出 0。
// ⚠ rng() 一律先落到具名变量再传参。

#include <bits/stdc++.h>
using namespace std;

static string randDigits(mt19937_64& rng, int len) {
    string s;
    s += char('1' + (int)(rng() % 9ull));
    for (int i = 1; i < len; i++) s += char('0' + (int)(rng() % 10ull));
    return s;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937_64 rng(seed * 1000003ull + 20260901ull);

    if (mode == 0) {
        unsigned long long a = 1 + rng() % 1000000000000000000ull;
        unsigned long long b = 1 + rng() % 1000000000000000000ull;
        printf("%llu\n%llu\n", a, b);
        return 0;
    }
    int len = (mode == 1) ? 200 : 10000;
    if (mode == 3) {
        // a 和 b 只差一点点 ⇒ 更相减损要减很多次
        string sa = randDigits(rng, len);
        printf("%s\n", sa.c_str());
        // b = a - 2（保持同奇偶时差为偶，减法版会一直小步走）
        string sb = sa;
        int i = (int)sb.size() - 1;
        while (i >= 0 && sb[i] == '0') { sb[i] = '9'; i--; }
        if (i >= 0 && sb[i] > '1') sb[i]--; else if (i >= 0) sb[i] = '1';
        printf("%s\n", sb.c_str());
        return 0;
    }
    if (mode == 4) {
        // 两个数都含大量公共的 2：造 odd * 2^k 的十进制串不方便，
        // 改成都乘以 1024（= 2¹⁰）的若干次 —— 用末尾补 0 近似不行（那是 10 的幂，含 2 也含 5）
        // ⇒ 直接让两个数都是偶数且低位大量相同：取同一个前缀 + 不同后缀，再各乘 2
        string base = randDigits(rng, len - 1);
        printf("%s0\n", base.c_str());            // 末尾 0 ⇒ 含因子 2 和 5
        printf("%s0\n", base.c_str());
        return 0;
    }
    printf("%s\n%s\n", randDigits(rng, len).c_str(), randDigits(rng, len).c_str());
    return 0;
}

// P2152 的度量程序：./p2152Count csv        （本页的数字都出自它）
//
//   rounds : ★★★ 换一把**机器无关**的尺子 —— 两种算法各走了多少轮。
//            二进制 gcd 每轮至少把一个数除以 2 ⇒ 轮数 O(log a + log b)；
//            而只做减法的版本，最坏要减 a/b 次。
//   ratio  : ★ 轮数 ÷ 总二进制位数 —— 用来印证「每轮至少减半一次」那条界。
//   small  : ★ 「用 unsigned long long 读」那一版的触发线：**超过 19 位就装不下**。
//   ms     : 一万位上两种算法的毫秒（⚠ 进程内计时，不含读入）。
//
// ⚠ 减法版必须有出口：超过 STEP_LIMIT 步就记成「跑不完」（不然这份程序自己会挂住闸门）。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static const unsigned BASE = 100000000u;
static const int W = 8;
static const long long STEP_LIMIT = 3000000;

struct Big {
    vector<unsigned> d;
    void trim() { while (d.size() > 1 && d.back() == 0) d.pop_back(); }
    bool isZero() const { return d.size() == 1 && d[0] == 0; }
    bool isEven() const { return (d[0] & 1u) == 0; }
};
static Big fromString(const string& s) {
    Big r;
    for (int i = (int)s.size(); i > 0; i -= W) { int l = max(0, i - W); r.d.push_back((unsigned)stoul(s.substr(l, i - l))); }
    if (r.d.empty()) r.d.push_back(0);
    r.trim(); return r;
}
static string toString(const Big& a) {
    string s = to_string(a.d.back());
    for (int i = (int)a.d.size() - 2; i >= 0; i--) { string t = to_string(a.d[i]); s += string(W - t.size(), '0') + t; }
    return s;
}
static int cmp(const Big& a, const Big& b) {
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1;
    for (int i = (int)a.d.size() - 1; i >= 0; i--) if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
    return 0;
}
static void sub(Big& a, const Big& b) {
    long long borrow = 0;
    for (size_t i = 0; i < a.d.size(); i++) {
        long long cur = (long long)a.d[i] - borrow - (i < b.d.size() ? (long long)b.d[i] : 0);
        if (cur < 0) { cur += BASE; borrow = 1; } else borrow = 0;
        a.d[i] = (unsigned)cur;
    }
    a.trim();
}
static void halve(Big& a) {
    unsigned rem = 0;
    for (int i = (int)a.d.size() - 1; i >= 0; i--) {
        unsigned long long cur = (unsigned long long)rem * BASE + a.d[i];
        a.d[i] = (unsigned)(cur >> 1); rem = (unsigned)(cur & 1ull);
    }
    a.trim();
}
static void twice(Big& a) {
    unsigned carry = 0;
    for (size_t i = 0; i < a.d.size(); i++) {
        unsigned long long cur = (unsigned long long)a.d[i] * 2 + carry;
        a.d[i] = (unsigned)(cur % BASE); carry = (unsigned)(cur / BASE);
    }
    if (carry) a.d.push_back(carry);
}

/** 二进制 gcd，返回轮数 */
static long long binGcd(Big a, Big b, string& out) {
    long long shift = 0, rounds = 0;
    while (a.isEven() && b.isEven()) { halve(a); halve(b); shift++; }
    while (!a.isZero()) {
        while (a.isEven()) halve(a);
        while (b.isEven()) halve(b);
        if (cmp(a, b) >= 0) sub(a, b); else sub(b, a);
        rounds++;
    }
    while (shift--) twice(b);
    out = toString(b);
    return rounds;
}
/** 只做减法，返回步数（跑不完给 −1） */
static long long subGcd(Big a, Big b) {
    long long steps = 0;
    while (!a.isZero() && !b.isZero()) {
        int c = cmp(a, b);
        if (c == 0) break;
        if (c > 0) sub(a, b); else sub(b, a);
        if (++steps > STEP_LIMIT) return -1;
    }
    return steps;
}

static string randDigits(mt19937_64& rng, int len) {
    string s; s += char('1' + (int)(rng() % 9ull));
    for (int i = 1; i < len; i++) s += char('0' + (int)(rng() % 10ull));
    return s;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");
    mt19937_64 rng(20260901ull);

    struct Row { const char* name; int len; bool close; };
    Row rows[3] = { {"200 位随机", 200, false}, {"一万位随机", 10000, false}, {"★ 一万位、两数只差 1", 10000, true} };
    long long binR[3], subR[3];
    double binMs[3], subMs[3];
    string ans[3];

    for (int i = 0; i < 3; i++) {
        string sa = randDigits(rng, rows[i].len), sb;
        if (rows[i].close) {
            sb = sa;
            int j = (int)sb.size() - 1;
            while (j >= 0 && sb[j] == '0') { sb[j] = '9'; j--; }
            if (j >= 0 && sb[j] > '1') sb[j]--; else if (j >= 0) sb[j] = '1';
        } else sb = randDigits(rng, rows[i].len);
        Big a = fromString(sa), b = fromString(sb);
        auto t0 = steady_clock::now();
        binR[i] = binGcd(a, b, ans[i]);
        binMs[i] = duration<double, milli>(steady_clock::now() - t0).count();
        t0 = steady_clock::now();
        subR[i] = subGcd(a, b);
        subMs[i] = duration<double, milli>(steady_clock::now() - t0).count();
    }

    /* 「每轮至少减半一次」那条界：轮数 ÷ 总二进制位数 */
    double bits2 = 10000 * 3.3219;               // 一万位十进制 ≈ 33219 个二进制位
    double ratio = binR[1] / bits2;

    /* p2152Small 的触发线：unsigned long long 最多装 19 位十进制 */
    int smallLine = 20;                          // 20 位就可能超 1.8×10¹⁹

    /* ★★★ 200 位那一档：为什么「装不下」那一版只被抓不到三成 —— 数一数就知道 */
    //   随机的 200 位数**往往互质**（正解答 1），而截断到 2⁶⁴ 之后的两个数**也往往互质**
    //   ⇒ 两版一起输出 1 ⇒ [「一致有两种：都算对了，和都没算」](/sol/p1746/) 的又一次。
    int trueOne = 0, truncOne = 0, differ = 0;
    {
        // ⚠ **复刻 p2152Gen.cpp 档 1 的种子公式**（否则量出来的数和对拍表对不上 —— 踩过一次）
        for (int seed = 1; seed <= 60; seed++) {
            mt19937_64 r2(seed * 1000003ull + 20260901ull);
            string sa = randDigits(r2, 200), sb = randDigits(r2, 200);
            Big a = fromString(sa), b = fromString(sb);
            string g;
            binGcd(a, b, g);
            if (g == "1") trueOne++;
            // 截断：只保留末 19 位（unsigned long long 大致能装的范围）
            unsigned long long ta = 0, tb = 0;
            for (char c : sa) ta = ta * 10 + (unsigned)(c - '0');
            for (char c : sb) tb = tb * 10 + (unsigned)(c - '0');
            unsigned long long x = ta, y = tb;
            while (y) { unsigned long long t = x % y; x = y; y = t; }
            if (x == 1) truncOne++;
            if (to_string(x) != g) differ++;
        }
    }

    if (csv) {
        for (int i = 0; i < 3; i++)
            printf("binR%d,%lld\nsubR%d,%lld\nbinMs%d,%.0f\nsubMs%d,%.0f\n", i, binR[i], i, subR[i], i, binMs[i], i, subMs[i]);
        printf("ratio,%.2f\nsmallLine,%d\n", ratio, smallLine);
        printf("trueOne,%d\ntruncOne,%d\ndiffer,%d\n", trueOne, truncOne, differ);
        printf("subTooSlow,%d\n", subR[2] < 0 ? 1 : 0);
        return 0;
    }
    printf("换一把机器无关的尺子：两种算法各走了多少轮（⚠ 减法版超过 %lld 步就记成「跑不完」）\n\n", STEP_LIMIT);
    printf("  %-24s %14s %14s   %10s %10s\n", "数据", "二进制 gcd 轮数", "只做减法 步数", "毫秒", "毫秒");
    for (int i = 0; i < 3; i++) {
        char buf[32];
        if (subR[i] < 0) snprintf(buf, sizeof(buf), "跑不完");
        else snprintf(buf, sizeof(buf), "%lld", subR[i]);
        printf("  %-24s %14lld %14s   %10.0f %10.0f\n", rows[i].name, binR[i], buf, binMs[i], subMs[i]);
    }
    printf("\n  ★ 一万位 ≈ %.0f 个二进制位，而二进制 gcd 只走了 %lld 轮 ⇒ 轮数 / 位数 = **%.2f**\n",
           bits2, binR[1], ratio);
    printf("    ⇒ 「每轮至少把一个数除以 2」那条界，在这儿是实打实的。\n");
    printf("\n  ★ 而「用 unsigned long long 读」那一版的线：**超过 19 位就装不下**（上限 1.8×10¹⁹）。\n");
    printf("    ⚠⚠ 可它在 200 位那一档只被抓 **%d / 60** —— 因为随机的 200 位数**往往互质**：\n", differ);
    printf("       正解答 1 的有 %d 轮，而截断之后 gcd 也是 1 的有 %d 轮 ⇒ **两版一起输出 1**。\n", trueOne, truncOne);
    return 0;
}