题解 | #大整数的因子#

#include <iostream>
#include <iterator>
#include <bits/stdc++.h>
using namespace std;

struct bign {
    int nums[3001];
    int lens;
    bign() {
        memset(nums, 0, sizeof(nums));
        lens = 0;
    }
};

bign multiply(bign a, bign b) {
    bign res;
    int length;
    for (int i = 0; i < a.lens; i++) {
        int carry = 0;
        length = i;
        for (int j = 0; j < b.lens; j++) {
            int current = a.nums[i] * b.nums[j] + carry;
            int jinwei = res.nums[length] + current;
            res.nums[length++] = jinwei % 10;
            carry = jinwei / 10;
        }
        if (carry) res.nums[length++] += carry;
    }
    res.lens = length;
    return res;

}

bign int2big(int num) {
    bign res;
    while (num > 0) {
        int t = num % 10;
        res.nums[res.lens++] = t;
        num /= 10;
    }
    return res;
}
bign str2big(string str){
    bign res;
    res.lens = str.size();
    for(int i = res.lens - 1; i >= 0; i--){
        res.nums[i] = str[res.lens - i - 1] - '0'; //切记 字符串转换big 要减去 ‘0’
    }
    return res;
}


bign jiecheng(int n) {
    bign ans = int2big(n);
    if (n == 1) return ans;
    return multiply(ans, jiecheng(n - 1));
}

bign divide(bign a, int b, int &remainder){ //big 除法 r用做余数
      bign res;
      res.lens = a.lens;
      remainder = 0;
      for(int i = a.lens - 1; i >= 0; i--){
        int current = a.nums[i] + remainder * 10; //当前位 加上上一位余位
        res.nums[i] = current / b; //本位可以先为0 后面会处理
        remainder = current % b; //余数计算更新
        // if(current % b== 0) {
        //     res.nums[i] = a.nums[i] / b;
        // }else{
        //     if(i != a.lens - 1 || current / b != 0){
        //         res.nums[i] = a.nums[i] / b;
        //         remainder = current % b;
        //     }
        // }
      }
      while(res.nums[res.lens - 1] == 0 && res.lens > 1) res.lens--; //更新res长度 从末尾遍历 如果为0则减一 但是如果只有一位时 就保留为0
      return res;

}




int main() {
    string n;
    while (cin >> n) {
        if(n == "-1") {
            break;
        }
        bign num = str2big(n);
        int count = 0;
        for(int k = 2; k <= 9; k++){
             int r;
             divide(num, k,r);
             if( r == 0) {
               cout << k << " ";
               count++;
             }
        }
        if(count == 0) cout << "none";
        cout << endl;
       

    }
}
// 64 位输出请用 printf("%lld")