Posted on 2010-08-19 15:35
Brian 阅读(273)
评论(0) 编辑 收藏 引用 所属分类:
SGU
f(n) 是正整数n 的各位数字之和。如果 f(n) 是1位数那么n的数根就是f(n)，否则f(n) 的数根就是n 的数根。举例说明：987的数根是6 (9+8+7=24 2+4=6)。你的任务是找出这样表达式的数根: A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1。
输入包含K个测试样例。输入第一行会给出 K (1<=K<=5)。每个测试样例占一行。这一行的第一个数是一个正整数N (N<=1000)。 接着是N个非负整数 (序列 A)。 均不超过109。
数根(百度知道):
http://zhidao.baidu.com/question/29789035.html对于求余数的问题是我一开始就忽略了的地方，后来看了HPF的博客，才知道有这样的技巧:
(A+B)mod C = (A mod C) + (B mod C)
(AB) mod C = (A mod C) × (B mod C)
C编译器 , 0MS 0KB , 如果你把前两句定义变量的语句对调，将会耗费 20MS 的时间
#include <stdio.h>
int main()
{
int i=0,j,K,N,temp,m;
long int A;
scanf("%d",&K);
for (; i<K; i++) {
scanf("%d",&N);
m=1;
A=0;
for (j=0; j<N; j++) {
scanf("%d",&temp);
temp%=9;
m=(m*temp)%9;
A=(A+m)%9;
}
printf("%d\n",(A+8)%9+1);
}
return 0;
}