题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=118

题目大意

定义f(n)为n各位数字之和，如果n是各位数，则n个数根是f(n)，否则为f(n)的数根。

现在给出n个Ai，求出 A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1 这个式子的数根。

题解

定义d(n)为n的数根，利用数学归纳法可证明(从N=1的情况向上递推)：

1、d( A1*A2* … *AN ) = d( AN * d( A1*A2* … *AN-1 ) ) 

2、d(A1 + A2 ) = d( d(A1) +d(A2) )

知识点

数根是自然数的一种性质，换句话说，每个自然数都有一个数根。数根是将一正整数的各个位数相加(即横向相加)，若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。

例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。 

公式法求数根：

a的数根b = ( a - 1) % 9 + 1

另外还有一个结论要记：任何一个整数模9同余于它的各数位上数字之和。

具体证明过程如下：

设自然数N=a[n]a[n-1]…a[0]，其中a[0]，a[1]、…、a[n]分别是个位、十位、…上的数字

再设M=a[0]+a[1]+…+a[n]

求证：N≡M(mod 9). 

证明：

因为 N=a[n]a[n-1]…a[0]=a[n]*10^n+a[n-1]*10^(n-1)+…+a[1]*10+a[0]

又因为 1≡1(mod 9), 10≡1(mod 9), 10^2≡1(mod 9), … 10^n≡1(mod 9)

上面这些同余式两边分别同乘以a[0]、a[1]、a[2]、…、a[n]，再相加得：

a[0]+a[1]*10+…+a[n]*10^n≡(a[0]+a[1]+…+a[n])(mod 9)， 即 N≡M(mod 9)，得证。

代码 

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int ans = 0, t = 1;
        while (n--) {
            int a;
            scanf("%d", &a);
            t = t*(a % 9) % 9;
            ans += t;
        }
        ans %= 9;
        if (ans == 0) printf("9\n");
        else printf("%d\n", ans);
    }
    return 0;
}

转载保留版权：http://haipz.com/blog/i/6456 - 海胖博客