题解 | #大整数的因子#

方法一：用字符串实现乘法和除法，先除再乘，如果能够还原则代表模为零

#include <iostream>
#include <vector>
using namespace std;
string divide(string a, int k) {
    int remainder = 0;
    for (int i= 0; i < a.size(); i++) {
        int temp = remainder * 10 + a[i] - '0';
        a[i] = temp / k + '0';
        remainder = temp % k;
    }
    int pos = 0;
    while (a[pos] == 0) pos++;
    return a.substr(pos);
}
string multiply(string a, int b) {
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        int temp = (a[i] - '0') * b + carry;
        a[i] = temp % 10 + '0';
        carry = temp/10;
    }
    while (carry != 0) {

        a = char(carry % 10 + '0') + a;
        carry /= 10;
    }
    return a;
}
bool canModZero(string a, int k) {
    string temp = divide(a, k);
    string tempMul = multiply(temp, k);
    if (tempMul == a) return true;
    else return false;
}
int main() {
    string c;
    while (cin >> c) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        if (c == "-1") break;
        vector<int> ks;
        for (int i = 2; i <= 9; i++) {
            if (canModZero(c, i)) ks.push_back(i);
        }
        if (ks.size() == 0) cout << "none" << endl;
        else {
            for (int i = 0; i < ks.size() - 1; i++) {
                cout << ks[i] << ' ';
            }
            cout << ks[ks.size() - 1]<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")

方法二：再做除法时已经得到了余数，余数为零代表能整除

#include <iostream>
#include <vector>
using namespace std;
int divide(string a, int k) {
    int remainder = 0;
    for (int i= 0; i < a.size(); i++) {
        int temp = remainder * 10 + a[i] - '0';
        a[i] = temp / k + '0';
        remainder = temp % k;
    }
    return remainder;
}
int main() {
    string c;
    while (cin >> c) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        if (c == "-1") break;
        vector<int> ks;
        for (int i = 2; i <= 9; i++) {
            if (divide(c, i)==0) ks.push_back(i);
        }
        if (ks.size() == 0) cout << "none" << endl;
        else {
            for (int i = 0; i < ks.size() - 1; i++) {
                cout << ks[i] << ' ';
            }
            cout << ks[ks.size() - 1]<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")