题解 | 大整数的因子

#include <algorithm>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

string delive(string s,int x)
{
    int car = 0;
    for(int i=0;i<s.size();i++)
    {
        int num = car*10 + (s[i]-'0');
        s[i] = num/x + '0';
        car = num%x;
    }
    while(s[0]=='0')s.erase(0,1);
    if(s=="")s="0";
    return s;
}

string Mul(string s1,string s2)
{
    int l1 = s1.size(),l2 = s2.size();
    if(l1<l2)swap(s1,s2);
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());
    int len = l1+l2+2;
    int ans[len];
    memset(ans,0,sizeof(ans));
    for(int i=0;i<s1.size();i++)
    {
        for(int j=0;j<s2.size();j++)
        {
            ans[i+j] +=(s1[i]-'0')*(s2[j]-'0');
        }
    }
    string s="";
    for(int i=0;i<len;i++)
    {
        int num = ans[i]/10;
        ans[i] %= 10;
        ans[i+1] += num;
        char c = ans[i]+'0';
        s = s+c;
    }
    reverse(s.begin(),s.end());
    while(s[0]=='0')s.erase(0,1);
    if(s=="")s="0";
    return s;


}

int main() {
    string s;
    while(cin>>s&&s!="-1")
    {
        while(s[0]=='0')s.erase(0,1);
        int flag = 0;
        for(int i=2;i<=9;i++)
        {
            
            string ans = delive(s,i);
            string now = "";
            char c = i+'0';
            now = now+c;
        //    cout<<ans<<endl;
            string ss = Mul(ans,now);
      //      cout<<ss<<endl;
            if(ss==s)
            {
                cout<<i<<" ";
                flag = 1;
            }
        }
        if(!flag)cout<<"none";
        cout<<endl;
        

            
    }
  //  cout<<delive("30",4)<<endl;
 // cout<<Mul("30","9");
}
// 64 位输出请用 printf("%lld")