快速幂模 a^b%p

2019-04-13 17:02发布

站内文章 / 模拟电子
9523 0 1433
class="markdown_views prism-atom-one-light">

经典版

#include using namespace std; typedef long long ll; ll work(ll base, ll exponent, ll mod) { ll temp = 1; while (exponent != 0) { if (exponent % 2 == 1) { exponent--; temp = (temp*base) % mod; } else { exponent /= 2; base = (base*base) % mod; } } return temp; }

使用位运算优化

ll work(ll base, ll exponent, ll mod) { ll temp = 1; while (exponent) { if (exponent & 1)//奇数 { temp = (temp * base) % mod; } exponent >>= 1;//相当于/2 base = (base*base) % mod; } return temp; }

热门文章