Table of Contents

SGU118 解题手记
　　搞的那么玄虚，实际上k的“数根”就是k除以9的余数（余数为0的当作余数为9处理）。设k=a0*10^0+a1*10^1+...+an*10^n，f(k)=a0+a1+...+an，则k与f(k)关于9同余，而root(k)=f(f(...f(k)...))，所以k与root(k)关于9同余。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//AC
#include <iostream>
using namespace std;
 
inline long root(long k)
{
    return k%9>0 ? k%9 : 9;
}
 
int main()
{
    long testcase,n,p,result,r;
    cin>>testcase;
    for (;testcase>0;--testcase)
    {
        result=0; r=1;
        cin>>n;
        for (;n>0;--n)
        {
            cin>>p;
            r=root(root(p)*r);
            result=root(result+r);
        }
        cout<<result<<endl;
    }
    return 0;
}