首页 > ACM题库 > 九度OJ > 九度-1125-大整数的因子[解题代码]
2013
12-12

九度-1125-大整数的因子[解题代码]

题目来源:2008年北京大学方正实验室计算机研究生机试真题

题目描述:

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

输入:

若干个非负整数c,c的位数<=30
每行一个c,当c=-1时中止
(不要对-1进行计算!)

输出:

每一个c的结果占一行
1) 若存在满足 c%k == 0 的k,输出所有这样的k,中间用空格隔开,最后一个k后面没有空格。
2) 若没有这样的k则输出"none"

样例输入:
30
72
13
-1
样例输出:
2 3 5 6
2 3 4 6 8 9
none
提示:

注意整数溢出问题
不要对-1进行计算


cpp 代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
	char s[31];
	int ans[10];
	int isFirst, i, tmp, len, l1, l3, sum, m7;
	while (gets(s), s[0] != '-') {
		for(i=2; i<=9; i++) ans[i]=0;
		isFirst = 0;
		sum = 0;
		m7 = 0;
		len = strlen(s);
		l1 = s[len - 1] - '0';
		if (len >= 3)
			l3 = (s[len - 3] - '0') * 100 + (s[len - 2] - '0') * 10 + l1;
		else if (len == 2)
			l3 = (s[len - 2] - '0') * 10 + l1;
		else
			l3 = l1;
		for (i = 0; i < len; i++) {
			tmp = s[i] - '0';
			sum += tmp;
			m7 *= 10;
			m7 = (m7 + tmp) % 7;
		}
		if (m7 % 7 == 0) ans[7]=1;
		if ((l3 & 7) == 0) ans[8] = ans[4] = ans[2] = 1;
		else if((l3 & 3) == 0) ans[4] = ans[2] = 1;
		else if ((l1 & 1) == 0) ans[2]=1;
		if (sum % 9 == 0) ans[9]=ans[3]=1;
		else if(sum % 3 == 0) ans[3]=1;
		if(ans[3] && ans[2]) ans[6]=1;
		if(l1==0 || l1==5) ans[5]=1;
		for(i=2; i<=9; i++){
			if(ans[i] && !isFirst){
				printf("%d",i);
				isFirst=1;
			}
			else if(ans[i]) printf(" %d",i);
		}
		if (!isFirst)
			printf("none");
		printf("\n");
	}
	return 0;
}
/**************************************************************
	Problem: 1125
	User: coder
	Language: C
	Result: Accepted
	Time:10 ms
	Memory:912 kb
****************************************************************/


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。