[[快速幂]]

快速乘

问题:

  1. 对于两个大数相乘取模有可能在乘完之后发生溢出
  2. 两数相乘由于底层原因导致时间不是最优

前置知识

快速幂

代码

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
ll getMul(ll x, ll y, ll mod){
    ll res = 0;
    while(y){
        if(y & 1){
            res = (res + x) % mod;
        }
        x = (x << 1) % mod;
        y >>= 1;
    }
    return res;
}