数论-快速幂-快速乘

快速幂：求 a^b % p

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 LL qmi(LL a, LL b, LL p){
 7     LL res = 1 % p;
 8     while(b){
 9         if(b & 1)res = res * a % p;
10         a = a * a % p;
11         b >>= 1;
12     }
13     return res;
14 }

View Code

快速乘：a * b % p

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 ll qmul(ll a, ll b, ll p){
 7     ll res = 0;
 8     while(a){
 9         if(a&1) res = (res + b) % p;
10         b = b * 2 % p;
11         a >>= 1;
12     }
13     return res;
14 }
15 
16 int main(){
17     ll a, b, p;
18     cin >> a >> b >> p;
19     cout << qmul(a, b, p) << endl;
20 }

View Code