hdu1163-九余数定理&数学的常见结论哟-Eddy's digital Roots

九余数定理就是 数字n%9 等于n的各位数相加之和 %9…

所以就十分的nice了。当n很大的时候，我们就直接这样求了。

首先证明前有两个基本需要知道的规律

这是别人哒，

https://blog.csdn.net/techmonster/article/details/50113789

1.和的模 等于 模的和再取模 如：(15+7)%3 = (15%3+7%3)%3 逆运算亦可

2.积的模 等于 模的积再取模 如：(15*7)%3 = (15%3 * 7%3) %3 逆运算亦可

假设一个数是：A=an x 10^n + a(n-1) x 10^(n-1) + …… + a1 x 10^1 + a0, 按照题目的意思是将A的A次方相乘后将各位的位数相加，相加后判断是否<10，否的话继续将各位的位数相加，如此循环直到最后相加的数0< result <=9范围内。设A的A次方相乘后的值为M，则M和A一样，也可以写成M=bn x 10^n + b(n-1) x 10^(n-1) + …… + b1 x 10^1 + b0， 也可以这样写:M=bn x ((10^n-1)+1) + b(n-1) x ((10^(n-1)-1)+1) + …… + b1 x ((10^1)-1)+1 + b0， 即除了个位上的数外其余位数上的数都可以用bn=999…（（n-1）个9）+ 1表示，除去括号得：

M=（bn x 9999…+ bn) + (b(n-1) x 999…+b(n-1)+ b1 x 9 + b1 + b0;

代码：

#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=+;
int main()
{    int t;
     /*while(cin>>t){
          if(!t)break;
          int ans=1;
          for(int i=1;i<=t;i++){
             ans=(ans*t)%9;
          }
        if(!ans)puts("9");
        else printf("%d\n",ans);
     }*/
     while(cin>>t){
           if(!t)break;
           int num=t;
           int ans=;
           while(t){
                if(t&){ans=(ans*num)%;
               // cout<<ans<<" "<<num<<" "<<t<<endl;
                }
                num=(num*num)%;
                t>>=;
                //cout<<t<<endl;
           }
           if(!ans)
            puts("9");
           else
            printf("%d\n",ans);
     }
    return ;
}