SGU118数学题Math

问题：令f(n)为n各个位数字之和。n的Digital Root是f(f(...f(n)))，是一位数字。现在给你A1,A2...An，n个数，求A1*A2*…*AN &＃43; A1*A2*…*AN-1 &＃43; … &＃43; A1*A2 &＃43; 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 &＃43; A1*A2*…*AN-1 &＃43; … &＃43; A1*A2 &＃43; A1.

解法：首先明确DR(A &＃43; B) = DR(DR(A) &＃43; DR(B))，继续推导有DR(A * B) = DR(DR(A) * DR(B))。

设S1 = A1*A2*…*AN &＃43; A1*A2*…*AN-1 &＃43; … &＃43; A1*A2 &＃43; A1，

DR(S1)

= DR(A1 &＃43; A1 * S2)

= DR(DR(A1) &＃43; DR(DR(A1)*DR(S2)))

= DR(DR(A1) &＃43; DR(DR(A1)*DR(A2 &＃43; A2*S3)))

= DR(DR(A1) &＃43; DR(DR(A1)*DR(A2)) &＃43; DR(DR(A1)*DR(A2)*DR(S3)))

=DR(Sum(DR(A1)*...*DR(Ai))) (i=1-->N)

#include
#include
#include
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;
}