模取幂运算 计算a^b mod n

2019-04-13 12:52发布

站内文章 / 模拟电子
13829 0 928
结合快速幂求a^b%n问题 以及如下公式 a^b % n = (a%n)^b % n (a * b)%n = ( (a%n)*(b%n) ) % n
#include using namespace std; #define ll long long ll ksm(ll a,ll b,ll n) { ll ans = 1; ll t = a%n; // a^b % n = (a%n)^b % n while(b) { if(b&1) ans = (ans * t)%n ; t = (t*t)%n; b >>=1; } return ans; } int main() { cout << ksm(2,7,7) <

热门文章