2925.md

大数取余 2925: 大整数的因子

题目要求判断给定的大整数是否能够被10以内的整数整除。

题目来源

2925: 大整数的因子

总时间限制: 1000ms 内存限制: 65536kB

描述

已知正整数k满足2<=k<=9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k。

输入

一个非负整数c，c的位数<=30。

输出

若存在满足 c%k == 0 的k，从小到大输出所有这样的k，相邻两个数之间用单个空格隔开；若没有这样的k，则输出"none"。

样例输入

30

样例输出

2 3 5 6 

由于是大整数，和之前的long long类型能够存储范围内的整数银子判断不同，需要以字符串的形式进行处理，由于除数都是个位数，可以按照整数除法竖式计算的方式逐步迭代到个位，看是否存在余数即可。

#include <iostream>
#include <string>
using namespace std;
int main() {
	string str;
	cin >> str;
	int i, j, q[10] = { 0 };
	for (i = 0; i < str.length(); ++i) {
		int num = str[i] - '0';
		for (j = 2; j <= 9; ++j) {
			q[j] = (num + q[j] * 10) % j;
		}
	}
	bool b = false;
	for (i = 2; i <= 9; ++i) {
		if (q[i] == 0) {
			b = true;
			cout << i << " ";
		}
	}
	cout << (b ? "" : "none") << endl;
	return 0;
}

2925.cpp 代码长度：411B 内存：200kB 时间：1ms 通过率：87% 最小内存：200kB 最短时间：0ms

初始余数支委0，输入字符串后，先将字符转换为数字，然后取余并保留余数，下一位须加上之前余数乘以10作为被除数继续取余到最后一位，如果余数为0则是因子。

有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。