数论模板

发表于 更新于 分类于 ， ，

模板算法

求 m^k mod p，时间复杂度 O(logk)。

1
2
3
4
5
6
7
8
9
10
11
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

计算 $\left \lceil m/n \right \rceil$ ：

1
int ans = (m + n - 1) / n;