问题：令f(n)为n各个位数字之和。n的Digital Root是f(f(...f(n)))，是一位数字。现在给你A1,A2...An，n个数，求A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1的Digitial Root。
Problem: Let f(n) be a sum of digits for positive integer n. If f(n) is one-digit number then it is a digital root for n and otherwise digital root of n is equal to digital root of f(n). For example, digital root of 987 is 6. Your task is to find digital root for expression A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1.
解法：首先明确DR(A + B) = DR(DR(A) + DR(B))，继续推导有DR(A * B) = DR(DR(A) * DR(B))。
设S1 = A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1，
DR(S1)
= DR(A1 + A1 * S2)
= DR(DR(A1) + DR(DR(A1)*DR(S2)))
= DR(DR(A1) + DR(DR(A1)*DR(A2 + A2*S3)))
= DR(DR(A1) + DR(DR(A1)*DR(A2)) + DR(DR(A1)*DR(A2)*DR(S3)))
=DR(Sum(DR(A1)*...*DR(Ai))) (i=1-->N)
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int a[1010],cas,n,ans,tt;
int f(int x) {
if (x<10) return x;
int sum = 0;
while (x) {
sum += x%10;
x /= 10;
}
return f(sum);
}
int main() {
scanf("%d",&cas);
while (cas--) {
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
ans = tt = f(a[1]);
for (int i=2;i<=n;i++) {
tt = f(tt*f(a[i]));
ans += tt;
}
printf("%d\n",f(ans));
}
return 0;
}