题解 | #大整数的因子# 无除法模拟高效算法

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

int main() {
    string s;
    while (cin >>s) { // 注意 while 处理多个 case
        if(s=="-1")return 0;
        int len=s.length();
        vector<int> ans;
        if((s[len-1]-'0')%2==0)ans.push_back(2);
        
        int sum=0;
        for(int i=0;i<len;i++)sum+=(s[i]-'0');
        if(sum%3==0)ans.push_back(3);
        
        sum=0;
        for(int i=max(0,len-2);i<len;i++){
            sum=sum*10+s[i]-'0';
        }
        if(sum%4==0)ans.push_back(4);
        
        if(s[len-1]=='0'||s[len-1]=='5')ans.push_back(5);
        
        if(find(ans.begin(),ans.end(),3)!=ans.end()&&find(ans.begin(),ans.end(),2)!=ans.end())ans.push_back(6);

        int a[6]={1,3,2,-1,-3,-2},k=0;
        sum=0;
        for(int i=len-1;i>=0;i--){
            sum+=(s[i]-'0')*a[(k++)%6];
        }
        if(sum%7==0)ans.push_back(7);
        sum=0;
        for(int i=max(0,len-3);i<len;i++){
            sum=sum*10+s[i]-'0';
        }
        if(sum%8==0)ans.push_back(8);

        sum=0;
        for(int i=0;i<len;i++)sum+=(s[i]-'0');
        if(sum%9==0)ans.push_back(9);

        if(!ans.size())cout<<"none"<<endl;
        else{
            for(int i=0;i<ans.size();i++){
                cout<<ans[i]<<" ";
            }cout<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")