题解 | 小红的 gcd

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#define int long long

using namespace std;

const int N=1e6+5;

string a;
int b;
vector<int>v;
int mo[N];

signed main()
{
    cin>>a>>b;
    int len=a.size();
    v.push_back(b);
    for(int i=sqrt(b);i>=1;i--)
    {
        if(b%i!=0) continue;
        if(i==sqrt(b)) v.push_back(i);
        v.push_back(b/i),v.push_back(i);
    }
    sort(v.begin(),v.end());
    int ans=0;
    mo[1]=10%b;
    mo[0]=1;
    for(int i=2;i<=len;i++) mo[i]=(mo[i-1]*mo[1])%b;
    for(int i=v.size()-1;i>=0;i--)
    {
        int tmp=v[i];
        int j=len-1;
        int res=0;
        while(j>=0) 
        {
            res=(res+(a[j]-'0')*mo[len-1-j]%tmp)%tmp;
            j--;
        }
        if(res==0)
        {
            ans=tmp;
            break;
        }
    }
    cout<<ans;
    return 0;
}