1690: 取余运算mod [3*]
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
取余运算mod
【问题描述】 输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。
【样例输入】2 10 9
【样例输出】7 (?明: 2^10 mod 9=7)
【知识准备】
进制转换的思想、二分法。
【算法分析】
本题主要的难点在于数据规模很大(b, p都是长整型数)，对于b^p显然不能死算，那样的话时间复杂度和编程复杂度都很大。
下面先介绍一个原理：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，求解的过程也就是将二进制数还原为十进制数的过程。
【问题描述】 输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。
【样例输入】2 10 9
【样例输出】7 (?明: 2^10 mod 9=7)
【知识准备】
进制转换的思想、二分法。
【算法分析】
本题主要的难点在于数据规模很大(b, p都是长整型数)，对于b^p显然不能死算，那样的话时间复杂度和编程复杂度都很大。
下面先介绍一个原理：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，求解的过程也就是将二进制数还原为十进制数的过程。