学步园

有关Digital_Root，大概就是求一个数的各个位之和，若这个数为个位数，则它即原数的DigitalRoot,若不是，则再对它进行数位求和。这个在网上看到有个公式是F(N)=(N-1)%9+1;证不出来，群里问了牛人，牛人果断几S解决了，ORZ......

牛人是这样提示我的：把N表达为sum(a[i]*10^i),sum(a[i]*10^i)=sum(a[i])(mod 9)....刚开始我没彻底懂，但知道了方向，后来才明白这是构造法

根据定义，F(a[i]*10^i) = F(sum(a[i]))，硬证不行，用构造法，根据上面的公式，F(X)=X%9成立。最后有个问题，当sum(a[i])<=9时,F(x) = X%9时不完全成立，F(X)=(A[I]-1)%9+1;

即证明F(x) = (X-1)%9 + 1(X>0) ,特别注意，当x=0时,f(x)=0

简单例题，SGU118，直接附代码：

#include <iostream>
#include <cstdio>
 
#define N 1010

using namespace std;
 
int a[N],n;

int f(int m)
{
    if (m>n) return 0;
    else return (a[m]%9)*(1+f(m+1))%9;
}

int main()
{
    int i,k;
    cin>>k;
    while (k--)
    {
        cin>>n;
        for (i=1;i<=n;i++) cin>>a[i];
        a[n+1]=0;
        if (a[1]==0) cout<<0<<endl;
        else 
        {
            int t = f(1);
            if (t==0) cout<<9<<endl;
            else cout<<t<<endl;
        }
    }
    return 0;
}