龟速乘

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
inline T mul(T x, T y, T mod) {
    x %= mod; y %= mod;
    T ans = 0;
    while (y) {
        if (y & 1) {
            ans = (ans + x) % mod;
        }
        x = (x + x) % mod;
        y >>= 1;
    }
    return ans;
}