hdu 1013 Digital Roots (九餘數定理)

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1013

題目大意：給定一個數，這個數的各位上的數相加的和，若這個數小于10，則相加的和為這個數的數根；反之，就重複操作，知道和小于10，得到這個數的數根。這個數可能很大，是以要用字元串來存儲。

分析：根據題目大意簡單模拟一邊，肯定都會。現在利用另一種方法，9餘數定理。定理證明：http://www.cnblogs.com/zzqc/p/6684794.html

ac代碼

#include<cstdio>
#include<cstring>
#define M 100005

char a[M];

int main()
{
    while(scanf("%s", a))
    {
        int num = 0;
        int len = strlen(a);
        for(int i = 0; i < len; i++)
            num = num + a[i] - '0';
        if(num == 0)return 0;
        int root = num % 9;
        if(root == 0)printf("9\n");
        else printf("%d\n", root);
    }
    return 0;
}