模算术

取模

设 $a$ 为整数，$n$ 为正整数，定义 - $ a \bmod n = a - \left \lfloor \frac{a}{n}\right \rfloor n ,(a \ge 0) $ - $ a \bmod n = -(-a \bmod n) ,(a \lt 0) $

这与 C++ 中的取模运算符的行为一致。

同余

若 $(a−b) \bmod n = 0 $，则称 $a$ 和 $b$ 同余，记为 $a≡b( \bmod n)$

$a$ 和 $b$ 均为正数时，此式等价于 $a \bmod n = b \bmod n$。

基本运算

模算术的基本性质 设 $a_0=a \bmod n，b_0=b \bmod n$，有 - $a+b≡a_0+b_0 \ \ \ \ ( \bmod n)$ - $a * b≡a_0 * b_0 \ \ \ \ ( \bmod n)$

对任意正整数 $k$，有 - $a \bmod n=(a \bmod k * n) \bmod n$

若 $k∣a$，有 - $\frac{a}{k} \bmod n=\frac{a \bmod k*n}{k}$

取模优化

template<class T>
inline T mod(T a) {
    return a < p ? a : a - p;
}

快速幂

求 $a^n \bmod p$，其中 $n$ 很大。

typedef long long LL;
LL pow(int a, int n) {
    LL res = 1;
    while(n) {
        if (n & 1)  res = 1LL * res * a % p;
        a = 1LL * a * a % p;
        n >>= 1;
    }
    return res;
}

龟速乘 / 快速加

求 $a \times k \bmod p$，其中 $k$ 很大。

typedef long long LL;

LL mul( LL a, LL k, LL p )
{
    LL res  = 0;
    while( k )
    {
        if ( k & 1 ) res = ( res + a ) % p;
        a = a * 2 % p;
        k >>= 1;
    }
    return res;
}

注记 快速幂有一个更直观的名字：平方求幂法。 类比这个名字，快速乘可以称为“加倍求积法”。毕竟，快速乘不仅完全不快，反而非常慢，称其为“快速”乘显得有些荒唐。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com