C++ 快速幂取模算法

2019-04-13 12:32发布

站内文章 / 模拟电子
11107 0 958

快速求b^p%k的值.

 

1 模运算与乘法的性质


 乘积取模可以在乘之前先取模 x * y % d = ((x % d) * (y % d)) % d; 比如：a*a%c = ((a % c) * ( a % c)) % c;  

2 本题公式


当b为偶数时：ab mod c = ((a2)b/2) mod c
当b为奇数时：ab mod c = ((a2)b/2× a) mod c

  因此快速幂实际是分治算法，每次将b分一半，直到b=0;

 
3 实现


 1> 递归实现 #include using namespace std; #define Lint long long Lint Mod(Lint a, Lint b, Lint c) { //求a的b次方 模c if(b == 0) return 1; //递归边界：0次幂=1 if(b % 2 == 1) return a * Mod(a*a % c, b/2, c) % c; //b是奇数时 else return Mod(a*a % c, b/2, c) % c; //b是偶数时 } int main() { Lint b, p, k; cin >> b >> p >> k; cout << b << "^" << p << " mod " << k << "=" << Mod(b, p, k) << endl; return 0; }

2> 非递归(循环)实现   #include using namespace std; #define Lint long long Lint mod(Lint a, Lint b, Lint c) { Lint ans = 1; while(b > 0) { if(b & 1) ans = ans * a % c; //位运算b&1与b%2相同 a = a * a % c; b >>= 1; //位运算：b/=2; } return ans; } int main() { Lint b, p, k; cin >> b >> p >> k; cout << b << "^" << p << " mod " << k << "="; cout << mod(b, p, k) % k << endl; }

热门文章