问题1007--取余运算mod [3*]

1007: 取余运算mod [3*]

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

取余运算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,求解的过程也就是将二进制数还原为十进制数的过程。

来源/分类