九餘數定理——hdu_1163 Eddy's digital Roots

九餘數定理（暫時先講一下自己的了解）

 （abc） % 9 = （a+b+c） % 9 ;

證明：（以3位數為例，如果不對，還望指正）

         ∵   (abc)=a * 10^3  + b * 10^2 + c   且   10^n % 9 =1

         ∴   (abc)%9 = (   ( a*10^3)%9    +   (b*10^2)%9   +   c%9   ) %9

                                = (   (a%9)%9      +   (b%9)%9     +     c%9  )%9

                                =  (  a + b + c )%9

        ∴     (abc)%9  =(a+b+c)%9

http://acm.hdu.edu.cn/showproblem.php?pid=1163

 而此題中要求（a+b+c）%9 ，我們利用（abc）%9 來求。

代碼：

//hdu 1163
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m;
    while(scanf("%d",&n),n){
        m=n;
        for(int i=0;i<n-1;i++){
            m = m*n%9;
        }
        if(!m) m=9;
        printf("%d\n",m);
    }
    return 0;
}