Skip to content

Latest commit

 

History

History
61 lines (48 loc) · 1.78 KB

2925.md

File metadata and controls

61 lines (48 loc) · 1.78 KB

大数取余 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。