NOI--大整数的因子

13:大整数的因子

描述

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

输入

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

输出

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

样例输入

30

样例输出

2 3 5 6

思路:

这是高精度除于单精度的题目，从高位到低位依次除以k，求余数，如果最后余数为0，说明能被k整除。

AC代码:

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

const int N = 30;

int a[N];

int main(){
	string s;
	int flag = 0;
	cin>>s;
	int len = s.length(); 
	//因为除是从高位往低位所以从高到低进行存储
	for(int i = 0; i < len; i++) {
	 	a[i] = s[i] - '0';
	 }
	for(int k = 2; k <= 9; k++) {
	 	int t = 0;
	 	for(int i = 0; i < len; i++) {
	 		t = t * 10 + a[i];
	 		t %= k;
		 }
		if(t == 0) {
		 	cout<<k<<" ";
		 	flag = 1;
		}
	}
	if(!flag) cout<<"none";
	return 0;
}