Posted on 2010-08-19 15:35
Brian 閱讀(303)
評論(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;
}