快速模取幂

2019-04-13 14:26发布

站内文章 / 模拟电子
9902 0 1477
计算 a^b mod c
法1：直接求解        [cpp] view plaincopy
  1. int ans =1;  
  2. for i=1 to b  
  3.     ans = ans * a;  
  4. ans = ans % c;  
法2：a^b mod c = ( a mod c ) ^ b mod c [cpp] view plaincopy
  1. int ans = 1;  
  2. a = a % c;  
  3. for i=1 to b  
  4.      ans = ans * a;  
  5. ans = ans % c;  

法3：由于某个因子取余后再相乘余数保持不变           a^b mod c = (a mod c)^b mod c                              =(...(((a mod c)*a) mod c)*a) mod c)...*a)mod c                                            共有b个a相乘 [cpp] view plaincopy
  1. int ans = 1;  
  2. a = a % c;  
  3. for i=1 to b  
  4.      ans = ans * a mod c;  
  5. ans = ans % c;  
法4：当b 为偶数时，a^b mod c = ( a^2 )^( b/2 ) mod c = k^( b/2 ) mod c 当b为奇数时，a ^b mod c = ( ( a^2 )^( b/2 ) )* a mod c = ( k^( b/2 )*a ) mod c [html] view plaincopy
  1. int ans= 1;  
  2. int k = a*a;  
  3. if b mod 2 equal 1  
  4.     ans = ( ans * a) mod c;  
  5. for i = 1 to b/2  
  6.     ans = ( ans * k) mod c;  
  7. ans = ans mod c;  

法5：对法4进行迭代，即：令 a = k; b = b/2; [cpp] view plaincopy
  1. int ans = 1, t = a;  
  2. while b > 0  
  3.    if b mod 2 equal 1  
  4.          ans = ( ans *t ) mod c;  
  5.    b /= 2;  
  6.    t = ( t *t ) mod c;  
  7. return ans;  

热门文章