4236: 取余运算mod
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：98
通过：41
题目描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。
输入格式
三个值 b，p，k
输出格式
bp mod k
输入样例 复制
2 10 9输出样例 复制
7数据范围与提示
本题主要的难点在于数据规模很大(b, p都是长整型数)，对于bp显然不能死算，那样的话时间复杂度和编程复杂度都很大。
下面先介绍一个原理：a*b mod k＝(a mod k)*(b mod k)mod k。
显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数P，有p＝2*p div 2+p mod 2，如19＝2*19 div 2十19 mod 2＝2*9+1，利用上述原理就可以把b的19次方除以k的余数转换为求b的9次方除以k的余数，即b19=b2*9+1＝b*b9*b9，再进一步分解 下去就不难求得整个问题的解。
这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，如p=19，有 19=2*9+1，9=2*4+1，4=2*2+0，2=2*1+0，1＝2*0+1，反过来，我们可以从0出发，通过乘以2再加上一个0或1而推出 1，2，4，9，19，这样就逐步得到了原来的指数，进而递推出以b为底，依次以这些数为指数的自然数除以k的余数。不难看出这里每一次乘以2后要加的数 就是19对应的二进制数的各位数字，即1，0，0，1，1，而19＝(10011)2，求解的过程也就是将二进制数还原为十进制数的过程。
下面先介绍一个原理：a*b mod k＝(a mod k)*(b mod k)mod k。
显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数P，有p＝2*p div 2+p mod 2，如19＝2*19 div 2十19 mod 2＝2*9+1，利用上述原理就可以把b的19次方除以k的余数转换为求b的9次方除以k的余数，即b19=b2*9+1＝b*b9*b9，再进一步分解 下去就不难求得整个问题的解。
这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，如p=19，有 19=2*9+1，9=2*4+1，4=2*2+0，2=2*1+0，1＝2*0+1，反过来，我们可以从0出发，通过乘以2再加上一个0或1而推出 1，2，4，9，19，这样就逐步得到了原来的指数，进而递推出以b为底，依次以这些数为指数的自然数除以k的余数。不难看出这里每一次乘以2后要加的数 就是19对应的二进制数的各位数字，即1，0，0，1，1，而19＝(10011)2，求解的过程也就是将二进制数还原为十进制数的过程。