九余数定理： 一个数对九取余后的结果称为九余数。 一个数的各位数字之和想加后得到的<10的数字称为这个数的九余数（如果相加结果大于9，则继续各位相加） 证明借鉴了网络上的证明，加以修改： 首先证明前有两个基本需要知道的规律  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;  题目条件表述说将各位上的数相加，对于上式来说即为将各位位数上的数乘上权值后对9的求模再相加（999…都能被9整除），得到的就是M1=bn+ b(n-1)+…+b1+b0（先不要想着将这一堆数按十进制进行相加，应想着这些数都是求模后剩下来的，等下还是要求模的）,  相加的数M1如果>=10，根据题目条件的意思又会继续循环相加，直至得到的Mn<10  此时Mn就为result（所需求的数）。 而这整个过程其实就是不断的求模的和，有 规律 1 的 逆运算 不断递归可知，其实真个运算等价于直接求 M%9 而M = N^N ，M极大，所以我们利用规律 2，结合 快速幂，求M%9#include #include #include #include using namespace std; #define MS(x,y) memset(x,y,sizeof(x)) void fr(){freopen("t.txt","r",stdin);} typedef long long LL; int main() { // fr(); int i,j,n,m,temp; while(~scanf("%d",&n) && n) { m = n%9; temp = 1; while(n>1) { if(n%2) temp *= m; m*=m; m %= 9; n/=2; } m = (m*temp)%9; if(m==0)printf("9 "); else printf("%d ",m); } }