算法笔记-数论

模板地址: GitHub

欧几里得算法(Euclid algorithm)

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

lcm(a, b) = a / gcd(a, b) * b

扩展欧几里得算法(exGCD)

目标: 寻找一对整数$(x, y)$,使$ax+by=gcd(a,b)$

void exgcd(LL a, LL b, LL& d, LL& x, LL& y) {
    if (!b) { d = a; x = 1; y = 0; }  //d为gcd(a, b)
    else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}

裴蜀定理

$ax+by=c$且$x,y$全为正整数,则当且仅当$gcd(a, b)|c$

素数相关

Eratosthenes筛法

bool vis[maxn];
int prime[maxn];
void getprime(int n) {
    int m = (int)sqrt(n + 0.5), num = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= m; ++i) if (!vis[i]) {
        prime[++num] = i;
        for (int j = i * i; j <= n; j += i) vis[j] = 1;
    }
}

欧拉线性筛

void getprime(int n) {
    vis[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            int v = i * prime[j];
            if (v > n) break;
            vis[v] = true;
        }
    }
}

素数定理

$$
\pi(x) \sim \frac{x}{\ln x}
$$

$Miller-Rabin$素数测试

原理:费马小定理
若$a^{n-1}\equiv 1\pmod n$,$a$取值越多,可以近似认为$n$为质数
使用二次探测定理改进卡卡迈尔数(合数$n$对于任何正整数$b$,都满足$gcd(b, n)=1\ \ b^{n-1}\equiv 1\pmod n$)的bug

LL Random(LL n) { return (LL)((double)rand() / RAND_MAX * n + 0.5); }
bool Witness(LL a, LL n) {
    LL m = n - 1; int j = 0;
    while (!(m & 1)) { j++; m >>= 1; }
    LL x = pow_mod(a, m, n);
    if (x == 1 || x == n - 1) return false;
    while (j--) { x = x * x % n; if (x == n - 1) return false; }
    return true;
}
bool Miller_Rabin(LL n) {
    if (n < 2) return false; if (n == 2) return true;
    if (!(n & 1)) return false;
    for (int i = 1; i <= 30; ++i) {
        LL a = Random(n - 2) + 1;
        if (Witness(a, n)) return false;
    }
    return true;
}

模算术

$$
(a + b)\bmod n = ((a\bmod n) + (b\bmod n))\bmod n\\
(a - b)\bmod n = ((a\bmod n) - (b\bmod n) + n)\bmod n\\
ab\mod n = (a\bmod n)(b\bmod n)\bmod n
$$

快速乘 $ab\bmod n$

LL mul_mod(LL a, LL b, LL n){
    LL res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % n;
        a = (a + a) % n;
        b >>= 1;
    }
    return res;
}

快速幂 $a^p\bmod n$

LL pow_mod(LL a, LL p, LL n) {
    if (p == 0 && n == 1) return 0;
    if (p == 0) return 1;
    LL ans = pow_mod(a, p / 2, n); ans = ans * ans % n;
    if (p % 2 == 1) ans = ans * a % n;
    return ans;
}

使用位运算:

LL pow_mod(LL a, LL p, LL n) {
    a %= n; LL ans = 1;
    for (; p; p >>= 1, a *= a, a %= n) if(p & 1) ans = ans * a % n;
    return ans;
}

欧拉$\varphi$函数

$$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$
$\varphi(n)$表示不超过$n$且与$n$互质的整数个数

求值

int euler_phi(int n) {
    int m = (int)sqrt(n + 0.5); int ans = n;
    for (int i = 2; i <= m; ++i) if (n % i == 0) {
        ans = ans / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

筛欧拉函数表

int phi[maxn];
void phi_table(int n) {
    for (int i = 2; i <= n; ++i) phi[i] = 0; phi[1] = 1;
    for (int i = 2; i <= n; ++i) if (!phi[i])
        for (int j = i; j <= n; j += i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
}

同余式定理

欧拉定理

若$gcd(a, n) = 1$,则$a^{\varphi(n)}\equiv 1\pmod n$

费马小定理

若$p$为质数,则$a^{p-1}\equiv 1\pmod p$

威尔逊定理

若$p$为质数,则$(p-1)!\equiv -1\pmod p$

乘法逆元

$$a\div b\bmod n = a\times b^{-1}\bmod n$$
$b^{-1}$称为$b$在模$n$意义下的逆元

$n$为质数

使用费马小定理, $a^{-1} = a^{n - 2}$

$n$不为质数

递归求解

LL inv(LL a, LL n) {
    LL d, x, y;
    exgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}

筛逆元表

int inv_table[maxn];
void getinv(int n, int p) {
    inv_table[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv_table[i] = (LL)(p - p / i) * inv_table[p % i] % p;
    }
}

同余方程

$ax\equiv b\pmod n$可以化为$ax+ny=b$使用扩展欧拉定理解决

中国剩余定理(China Remainder Theorem)

求解$x\equiv a_i\pmod {m_i}$满足$m_i$两两互质

LL crt(int n, int* a, int* m) {
    LL M = 1, d, y, x = 0;
    for (int i = 0; i < n; ++i) M *= m[i];
    for (int i = 0; i < n; ++i) {
        LL w = M / m[i];
        exgcd(m[i], w, d, d, y);
        x = (x + y * w * a[i]) % M;
    }
    return (x + M) % M;
}

扩展中国剩余定理(exCRT)

$m_i$不一定两两互质

LL excrt(LL n, LL* a, LL* m) {
    LL x, y, k, M = m[0], ans = a[0];
    for (int i = 1; i < n; ++i) {
        LL A = M, B = m[i], C = (a[i] - ans % B + B) % B, gcd;
        exgcd(A, B, gcd, x, y);
        LL bg = B / gcd;
        if (C % gcd != 0) return -1;
        x = mul_mod(x, C / gcd, bg);
        ans += x * M; M *= bg;
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}

离散对数(BSGS)

求解$a^x\equiv b\pmod n$满足$n$为质数

int log_mod(int a, int b, int n) {
    int m, v, e = 1, i;
    m = (int)sqrt(n + 0.5);
    v = inv(pow_mod(a, m, n), n);
    map<int, int> x;
    x[1] = 0;
    for (i = 1; i < m; ++i) {
        e = mul_mod(e, a, n);
        if (!x.count(e)) x[e] = i;
    }
    for (i = 0; i < m; ++i) {
        if (x.count(b)) return i * m + x[b];
        b = mul_mod(b, v, n);
    }
    return -1;
}

莫比乌斯反演

整除分块

整除分块可以对后面的莫比乌斯反演提供很大的优化
通过枚举可以发现$\lfloor \frac{n}{i} \rfloor$的结果会出现分块现象
例如$n=10$时
$\ \ \ i\ \ \ \ 1\ \ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ …$
$\lfloor \frac{n}{i} \rfloor\ 10\ 5\ 3\ 2\ 2\ 1\ 1\ 1\ 1\ 1\ \ \ 0\ \ \ 0\ \ \ 0\ \ \ …$
不难发现,每个块的右端点为$r=\lfloor \frac{n}{t}\rfloor (t=\lfloor \frac{n}{i}\rfloor)$

莫比乌斯函数

$$
\mu(n) =
\begin{cases}
1, & n=1 \\
(-1)^r, & n=p_1p_2p_3…p_r(\text{$p_i$为互不相同的质数}) \\
0, & else
\end{cases}
$$
性质:
$$\sum_{d|n}{\mu(d)}=[n=1]$$
$$\sum_{d|n}{\frac{\mu(d)}{d}}=\frac{\varphi(n)}{n}$$
线性筛:

int mu[maxn], vis[maxn];
int primes[maxn], cnt;
void get_mu(int n) {
	memset(vis, 0, sizeof(vis));
	memset(mu, 0, sizeof(mu));
	cnt = 0; mu[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) { primes[cnt++] = i; mu[i] = -1; }
		for (int j = 0; j < cnt && primes[j] * i <= n; ++j) {
			vis[primes[j] * i] = 1;
			if (i % primes[j] == 0)break;
			mu[i * primes[j]] = -mu[i];
		}
	}
}