http://acm.sgu.ru/problem.php?contest=0&problem=118
一开始是逐位逐位加求出digital root，结果超时了。
到网上看了一下，其实就是数n模9。可以证明如下：
设x = an* 10^(n-1) + ... + a1* 10^0 = an* (1+9)^(n-1) + ... + a1* (1+9)^0
所以x ≡
an + ... + a1 (mod 9)，递推下去即可得证。当取模等于0时，应该取9.
#include <stdio.h>
inline int DigitSum(int n);
int main(void) {
int k, n;
int d[1001] = {1};
scanf ("%d", &k);
int i, a;
while (k--) {
scanf ("%d", &n);
for (i = 0; i < n; ++i) {
scanf ("%d", &a);
d[i+1] = DigitSum(DigitSum(a)*d[i]);
}
int result = 0;
for (i = 1; i <= n; ++i) {
result += d[i];
}
printf ("%d\n", DigitSum(result));
}
return 0;
}
int DigitSum(int n) {
return (n%9) ? n%9 : 9;
}