题解 | #大整数的因子#
大整数的因子
https://www.nowcoder.com/practice/3d6cee12fbf54ea99bb165cbaba5823d
#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")