快速幂取模（2^n%10007)

2019-04-13 16:09发布

站内文章 / 模拟电子
14316 0 1542
思路分析：         1、最直观常规的想法，就是对做N次2的累乘。但显然对于大数据，数据会溢出。于是想到边乘变取模的方法，就是O(n)的复杂度，但是n的值最大可以取到1000000000，一样会超时，所以这种方法不可取。         2、于是想到Montgomery幂模运算来减少取模次数，快速运算a^b%k，只是RSA加密算法的核心之一。用此方法复杂度降到O(logn)。               在本题中，底数默认a=2，模k=10007。               采用二分的思想，例如求D=C^15%N 由于：a*b % n = (a % n)*(b % n) % n               所以令：                             C1 =C*C % N =C^2 % N                             C2 =C1*C % N =C^3 % N                             C3 =C2*C2 % N =C^6 % N                             C4 =C3*C % N =C^7 % N                             C5 =C4*C4 % N =C^14 % N                             C6 =C5*C % N =C^15 % N         即：对于E=15的幂模运算可分解为6 个乘模运算。
代码如下：
#include using namespace std; int main() { int n,a=2,b=1,m=10007; cin>>n; while(n) { if(n%2==1) b=(a*b)%m; a=(a*a)%m; n=n/2; } cout<
3、算法优化
      判断n能否被2整除，可以转化为判断该数的二进制位的末位是否为0。
      采用位与运算来判断n的奇偶性，n&1=0为偶数，n&1=1为奇数。n/2的工作通过采用右移运算符来实现。
      由于主要就一个while循环，而输入的变量位数是确定的（经过移位运算），故算法复杂度是O(1)。

代码如下：

#include using namespace std; int main() { int n,a=2,b=1,m=10007; cin>>n; while(n) { if(n&1==1) b=(a*b)%m; a=(a*a)%m; n>>=1; } cout<


      

热门文章