题目描述：

N<k时，root(N,k) = N，否则，root(N,k) = root(N',k)。N'为N的k进制表示的各位数字之和。输入x,y,k，输出root(x^y,k)的值 (这里^为乘方，不是异或)，2=<k<=16，0<x,y<2000000000，有一半的测试点里 x^y 会溢出int的范围(>=2000000000)

输入：

每组测试数据包括一行，x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)

输出：

输入可能有多组数据，对于每一组数据，root(x^y, k)的值

样例输入：

4 4 10

样例输出：

代码

 #include <stdio.h>
#define LL long long int
LL exp_mod(LL x,LL y,LL n){
    LL ret=1;
    while(y){
        if(y&1) ret=(ret*x)%n;
        x=(x*x)%n;
        y=y>>1;   
    }   
    return ret;
}

int main(){
    LL a,b,k,ans;

    while(scanf("%lld%lld%lld",&a,&b,&k)==3){
        ans=exp_mod(a,b,k-1);
        if(ans==0) ans=k-1;
        printf("%lld\n",ans);  
    }
    return 0;
}

作者提醒

自己的方法是构造bigint数据类型，然后无脑循环乘求幂，然后再转换k进制，递归求解。
这种做法的时间复杂度就不用说了，数据稍微一大一定超时。真正有效的做法代码很简单，
却需要很强的数学知识和严格证明，自知达不到这个水平，
果断引来大神的博客http://blog.sina.com.cn/s/blog_8619a25801010wcy.html快速幂取模。
原文如下：

计算x^ymod n;如果采用常规方法，当x与y都比较小的情况下，采用直接计算可以，
但是如果当x跟y都非常大的时候，如2^1000mod 100000，那该如何解决呢？
  利用模运算的这个：（a*b）mod n = (（a mod n） * b ) mod n;
  例如：2^11 mod 100 = 2^(1011) mod 100= （(2 ^(1010)mod 100)＊２）mod 100……
   1011为11的二进制表示
  于是就有如下的实现过程了：

#define LL long long int
LL exp_mod( LL x , LL y , LL n ){
     LL ret=1;
     while(y){
             if(y&1) ret=(ret*x)%n;
             x=(x*x)%n;
             y=y>>1;
     }
     return ret;
}

程序执行次数至于y的位长度有关。

实战例子：求root(N, k)

    2010年清华的上机题目，题意请点击题目处链接。

    本题可以有如下分析：

   N=a0+a1*k+a2*k^2+……+an*k^n;

   N'=a0+a1+a2+……+an;

   N-N'=a1*(k-1)+a2*(k^2-1)+……+an*(k^n-1);

   提取(k-1)有: (N-N')%(K-1)=0;

   继续递推下去有： （N-N'）%(k-1) =0；

                                （N'-N''）%(k-1)=0;

                                  ……

                                 （N(r-1)-N(r)）%（k-1）=0；

    相加有：（N-N(r)）%(k-1)=0,N(r)是我们要求的结果，故有

    N(r) = N % (k-1);

    如果 N(r)==0 ,为边界，则 N(r) = k-1;

     至于如何取模运算参考上面刚学习的快速幂取模即可。