题解 | #小红的 gcd#

算法思想

由于 的位数最大可达 ，无法直接存储为普通整数，而 在常规整数范围内。计算 可利用欧几里得算法的性质：

因此只需先求出 ，之后再用常规的欧几里得算法计算两数的最大公约数。

可通过模拟大数取模的过程：从左到右逐位处理，用当前余数 更新为

最终 即为所求余数。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a;
    ll b;
    cin >> a >> b;

    int len = a.size();
    ll va = 0;
    for (int i = 0; i < len; i++) {
        int d = a[i] - '0';
        va = va * 10 + d;
        va = va % b;
    }
    int ans = gcd(va, b);
    cout << ans << endl;
}