思路

先看一眼题，gcd，再看一眼数据，a 的十进制位数最大可以达到1e6！

这意味着a可能非常大! ！超过了long long类型所能表示的范围。

由于a过大，我们不能直接使用标准的欧几里得算法，因为a无法作为一个long long或者int类型传入计算。

核心处理

当 a是一个大数时， 欧几里得算法的操作仍然是可行的，因为：

1. 大整数 a可以用一个字符串str来表示。
2. 对一个大整数 a 求模 b，实际上就是不断地对 a 的各位数字进行处理，而中间的余数永远不会超过 b-1，

代码构思

步骤 1：求大数a对小数b的模

我们可以通过模拟长除法的过程来实现大数模小运算。

设 a的字符串表示为 str 。

初始化余数res 。

遍历字符串str中的每一个数字字符 c，

将当前余数 res乘以 10，并加上新的数字 c 对应的整数值，对结果进行求模 。

经过遍历，最终得到的 res就是 a(mod)b的结果。

步骤 2：使用欧几里得算法求gcd(a,b)

根据 ，现在问题转化为了求两个标准整数res和 b 的最大公约数。我们可以使用标准的欧几里得算法：

ACnode

#include <bits/stdc++.h>
using namespace std;
#define int long long
//万恶的dill
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x % y);
}/*用三目运算符表示欧几里得算法，等同于下面这个
    if (y == 0) 
    {
        return x;
    }
    return gcd(y, x % y);
    当然，也可以用迭代实现(我认为三目更好写一些())
    while (y) 
    {
        x %= y;
        swap(x, y);
    }
    return x;*/
void solve()
{
    string str;
    int b;
    cin >> str;// 输入大整数a (用字符串读取)
    cin >> b;
    int res = 0;
    for (char c : str)// 遍历大数a的每一位
    {
        res = (res * 10 + (c - '0')) % b;
        // 1. 将前一位的余数 * 10，并加上当前位数字的值
        //    (res * 10 + (c - '0'))
        // 2. 对结果进行求模 b，保证 res 始终在 [0, b-1] 范围内
    }
    int ans = gcd(res, b);
    cout<<ans<<endl;
}

signed main()
{
    int t = 1;
    //cin>>t;
    //个人码风，方便调试
    while (t--)
    {
        solve();
    }
    return 0;
}