浅淡数论

随手写写，就当是复习

顺序随机(因为我太菜了，所以只能想到什么写什么)

gcd

__gcd(a,b)

or

\(\gcd(a, b) = \gcd(a, b - a) = \gcd (b,a \% b)\)

inline int gcd(int a, int b)
{
	if (!b) return a;
	return gcd(b, a % b);
}

lcm

inline int lcm(int a, int b)
{
	return a / gcd(a, b) * b;
}

扩展欧几里得

求解关于 \(x,y\) 的不定方程

\(ax + by = \gcd(a, b)\)

根据欧几里得定理，\(\gcd(a, b) = \gcd(b, a\mod b)\)

于是

\(ax + by = \gcd(b, a \mod b) = bx + (a \mod b) y\)

\(\begin{align*} ax + by &= bx + (a - \lfloor \frac a b \rfloor \cdot b)y\\ &= bx + ay - \lfloor \frac a b \rfloor \cdot by\\ &= ay + b(x + \lfloor \frac a b \rfloor y) \end{align*}\)

于是

\(\left\{ \begin{align*} x' &= y\\y' &= x + \lfloor \frac a b \rfloor y \end{align*} \right.\)

inline int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a%b, x, y);
    int xx = y, yy = x - a / b * y;
    x = xx, y = yy;
    return g;
}

求解关于 \(x\) 的线性同余方程

\(ax \equiv b \mod m\)

原式等价于

\[ax + k_1m = b + k_2m\\ \Leftrightarrow ax + m(k_1 - k_2) = b\\ 令 g \leftarrow \gcd(a,m)\\ \Leftrightarrow a \cdot \frac g b x + m \cdot \frac g b (k_1 - k_2) = g \]

当且仅当 \(b \mid g\) 有解，直接用 exgcd 求解即可

线性筛素数

for (re int i = 2; i <= n; ++i)
{
    if (!vis[i]) pri[++num] = i;
    for (re int j = 1; j <= num && pri[j] * i <= n; ++j)
    {
        vis[i * pri[j]] = 1;
        if (i % pri[j] == 0) break;
    }
}

欧拉函数

Definition : \(a, b\) 互质是指 \(\gcd(a, b) = 1\)

求解 \(\varphi(n)\)

数学归纳法：

• 当 \(n\) 为质数时 \(\varphi (n) = n - 1\)

• 当 \(n\) 为合数时：

  1. \(n = p^a\) ：

     此时 \(n\) 的质因数只有 \(p\) ，那么在 \([1, p^a]\) 内不与 \(p^a\) 互质的数只有 \(p, 2p, 3p ...\) 共 \(\begin{align*} \frac {p^a} p \end{align*}\) 个

     小容斥一下，\(\begin{align*} \varphi(n) = p^a - \frac {p^a} p \end{align*}\)

     最终 \(\begin{align*} \varphi(n) = p^a (1 - \frac 1 p) \end{align*}\)

  2. others：

     根据算数基本定理，\(\begin{align*} n = \prod p_i^{a_i} \end{align*}\)

     又根据 \(y = \varphi (n)\) 为积性函数，\(\begin{align*} \varphi(n) = \varphi(\prod p_i^{a_i}) = \prod \varphi(p_i^{a_i}) = \prod p_i^a (1 - \frac 1 {p_i}) = \prod {p_i^a} \prod(1 - \frac 1 {p_i}) \end{align*}\)

     最终 \(\begin{align*} \varphi(n) = n\prod(1 - \frac 1 {p_i}) \end{align*}\)

线性筛欧拉函数

• Theorem 1 ：若 \(n\) 为质数 \(\varphi(n) = n - 1\)

• Theorem 2 ：若 \(p \mid n\)，则 \(\varphi(n \cdot p ) = \varphi (n) \cdot p\)

  Proof ：

  ​ \(\begin{align*} \because \varphi(n \cdot p) = n \cdot p(1 - \frac 1 p), \varphi(n) = n(1 - \frac 1 p) \end{align*}\)

  ​ \(\begin{align*} \therefore \frac {\varphi(n \cdot p)} {\varphi(n)} = p \end{align*}\) ，证毕

• Theorem 3 ：若 \(p \nmid n\)，则 \(\varphi(n \cdot p ) = \varphi(n) \cdot (p - 1)\)

  Proof ：

  ​ \(\varphi (n \cdot p ) = \varphi (n) \cdot \varphi (p) = \varphi(n) \cdot (p - 1)\) ，证毕

phi[1] = 1;
for (re int i = 2; i <= n; ++i)
{
    if (!vis[i]) pri[++num] = i, phi[i] = i - 1;
    for (re int j = 1; j <= num && pri[j] * i <= n; ++j)
    {
        vis[pri[j] * i] = 1;
        if(i % pri[j] == 0)
        {
            phi[i * pri[j]] = phi[i] * pri[j];//Theorem 2
            break;
        }
        phi[i * pri[j]] = phi[i] * (pri[j] - 1);
    }
}

欧拉定理

若 \(a\) 与 \(n\) 互质，则 \(a^{\varphi(n)} \equiv 1 \mod n\)，证明不会

欧拉定理推论

若 \(a\) 与 \(n\) 互质，则 \(a^b \equiv a^{b \mod \varphi(n)} \mod n\)

Proof ：

​ 设 \(b = q \varphi(n) + r\)，则 \(r = b \mod \varphi(n)\)

​ 于是 \(a^b = a^{q\varphi(n) + r} = a^{\varphi(n)^q} \cdot a^r\)

​ 根据欧拉定理，由于 \(a\) 与 \(n\) 互质，于是 \(a^{\varphi(n)} \equiv 1 \mod n\)

​ 于是 \(a^b\equiv 1^q \cdot a^r \equiv a^{b \mod \varphi(n)} \mod n\)，证毕

若 \(a\) 与 \(n\) 不互质，则 \(\begin{align*} a^b \equiv a^{b \mod \varphi(n) + \varphi(n)} \mod n \end{align*}\)，（当然，\(b > \varphi(n)\) ），证明不会

欧拉反演

\(\sum_{d\mid n} \varphi(d) = n\) 证明不会（这么多的证明我都不会，我真是太菜了/kk）

扩展中国剩余定理（EXCTR）

我不会中剩（CTR）

求解线性同余方程组：

\(\left\{ \begin{align*} x&\equiv a_1 \mod m_1\\ x&\equiv a_2 \mod m_2\\ x&\equiv a_3 \mod m_3\\ &...\\ x&\equiv a_n \mod m_n \end{align*} \right.\)

其中 \(m_1, m_2, m_3... m_n\) 可以不互质

设当前求出的解 \(x_{k-1}\) 满足前 \(k - 1\) 个方程，\(M\) 为 $\begin{align} LCM_{i = 1}^{k -1 } m_i \end{align} $

则第 \(k\) 个方程的解 \(x_k = x_{k-1} + tM\) 需满足 \(x_k \equiv a_k \mod m_k\)

即求解 \(t\in \mathbb{Z}\)，满足 \(tM \equiv a_k - x_{k-1} \mod m_k\)

方程中 \(x_{k-1}, M, a_k, m_k\) 都为已知量，只需用扩展欧几里得求解 \(n\) 次线性同余方程即可

n = read();
int m = read(), a = read();
X = a, M = m;
for (re int i = 2; i <= n; ++i)
{
    m = read(), a = read();
    int t, y;
    int b = ((a - X) % m + m) % m, g = exgcd(M, m, t, y);
    t = t * (b / g) % m;
    X = X + t * M;
    M = M / g * m;
    X = (X + M) % M;
}

逆元

Definition：若 \(ax \equiv 1 \mod m\)，则称 \(x\) 为 \(a\) 在模 \(m\) 意义下的逆元，当且仅当 \(a\) ，\(m\) 互质的情况下才存在逆元

1. 根据定义，求解用扩展欧几里得解线性同余方程求得逆元

2. 欧拉定理求逆元 ：根据 \(\begin{align*} a^{\varphi(n)} \equiv 1 \mod n \end{align*}\)，于是 \(a \cdot a^{\varphi(n) - 1} \equiv 1 \mod n\)，\(a^{\varphi(n) - 1}\) 即为逆元

3. 费马小定理求逆元 ：

   Definition : 当 \(n\) 为质数时，\(a^{n - 1} \equiv 1 \mod n\)

   Proof ：

   ​ 因为 \(m\) 为质数，于是 \(\varphi(n) = n - 1\)

   ​ 再根据欧拉定理可得 \(a^{\varphi(n)} = a^{n -1 } \equiv 1 \mod n\)，证毕

   因此 \(a \cdot a^{n - 2} \equiv 1 \mod n\)，\(a^{n - 2}\) 即为逆元

线性求逆元

设当前为 \(i\)，模数为 \(m\)，已知 \([inv_1,inv_{i-1}]\)，求 \(inv_i\)

设 \(m = qi + r\)，\(q,r\in \mathbb{Z} ,r<i\)，则 \(\begin{align*} q = \lfloor \frac m i \rfloor \end{align*}\)，\(r = m \% i\)

于是 \(m = qi + r \equiv 0 \mod m\)

两边同时除以 \(i \cdot r\)，有 \(q \cdot inv[r] + inv[i] \equiv 0 \mod m\)

于是 \(inv[i] \equiv -q \cdot inv[r] \mod m\)

带入 \(q,r\) 即为 ：\(\begin{align*}i nv[i] \equiv -\lfloor \frac m i \rfloor \cdot inv[m \% i]\mod m \end{align*}\)

为了保证 \(inv[i]\) 为正整数，\(\begin{align*}i nv[i] = m - \lfloor \frac m i \rfloor \cdot inv[m \% i] \% m \end{align*}\)

inv[1] = 1;
for (re int i = 2; i <= n; ++i)
	inv[i] = P - P / i * inv[P % i] % P;

线性求阶乘逆元

由于 \(\begin{align*} fac[i] = fac[i - 1] \cdot i \% P \end{align*}\)

于是可得 \(fac[i] \equiv fac[i - 1] \cdot i \mod P\)

两边同时除以 \(fac[i] \cdot fac[i - 1]\)，得 \(inv[fac[i - 1]] \equiv inv[fac[i]] \cdot i \mod P\)

于是可得 \(inv[fac[i]] = inv[fac[i + 1]] \cdot (i+1) %P\)

inv[n] = ksm(n, P - 2);//用快速幂求逆元(费马小定理)
for (re int i = n - 1; i; --i)
    inv[i] = inv[i + 1] * (i + 1) % P;

线性求任意数逆元

给定 \(n\) 个数 \(a_1,a_2,a_3...a_n\)，对于每一个 \(1 \le i \le n\)，求 \(a_i\) 的在模 \(P\) 意义下的逆元

设当前求 \(a_i\) 的逆元，\(\begin{align*} M = \prod_{i = 1}^n a_i \end{align*}\)，\(\begin{align*}pm ul_i = \prod_{j = 1} ^ i a_j \end{align*}\)，\(\begin{align*} smul = \prod _{j = i} ^ n a_j \end{align*}\)

则有 \(\begin{align*} pmul_{i-1} \cdot a_i \cdot smul_{i + 1} \equiv M \mod P \end{align*}\)

老规矩，两边同时除以 \(a_i \cdot M\)，得 \(\begin{align*}i nv[M] \cdot pmul_{i-1} \cdot smul_{i + 1} \equiv inv[a_i] \mod P \end{align*}\)

预处理出 \(pmul_i\) 和 \(smul_i\)，用 \(O(logM)\) 的时间复杂度算出 \(inv[M]\)，那么对于每个 \(a_i\)，可以用 \(O(1)\) 的时间复杂度算出 \(inv[a_i]\) 总时间复杂度为 \(O(n)\)

pmul[0] = smul[n + 1] = M = 1;
for (re int i = 1; i <= n; ++i)
{
    M = M * i % P;
    pmul[i] = pmul[i - 1] * i % P;
}
for (re int i = n; i; --i) smul[i] = smul[i + 1] * i % P;
int invM = ksm(M, P - 2);
for (re int i = 1; i <= n; ++i)
    inv[i] = invM * pmul[i - 1] % P * smul[i + 1] % P;

组合数学

\(\begin{align*} A_n^m = \frac {n!} {(n - m)!} \end{align*}\)，\(\begin{align*} C_n^m = \frac {n!}{m!(n-m)!} \end{align*}\)

求解组合数用公式算或用杨辉三角递推，具体如何选择看情况

Lucas定理

当 \(n,m \ge P\) 时，由于我们不能直接对 \(n, m\) 取模算组合数，所以就需要用到Lucas定理 ：

\(\begin{align*} C_n^m = C_{n \% P} ^ {m \% P} \cdot C_{n / p} ^ {m / p} \end{align*}\) ，证明不会

莫比乌斯函数

Definition ：

​ 设 \(\begin{align*} n = \prod_{i = 1} ^ m p_i^{c_i} \end{align*}\)

​ 则

\[\mu(n) = \left\{ \begin{align*} 0&\qquad \exists i \in [1, m], c_i > 1\\ 1&\qquad m \% 2=0,\forall i \in [1,m], c_i = 1\\ -1&\qquad m \% 2 = 1, \forall i \in [1,m],c_i = 1 \end{align*} \right. \]

​ 更通俗地

\[\mu(n) = \left\{ \begin{align*} 0&\qquad n能被某个质数的平方整除\\ 1&\qquad n是偶数个不同质数的积\\ -1&\qquad n是奇数个不同质数的积 \end{align*} \right. \]

线性筛莫比乌斯函数

根据定义很好理解，与线性筛欧拉函数很相似

mu[1] = 1;
for (re int i = 2; i <= n; ++i)
{
    if (!vis[i]) pri[++num] = i, mu[i] = -1;
    for (re int j = 1; j <= num && pri[j] * i <= n; ++j)
    {
        vis[i * pri[j]] = 1;
        if(i % pri[j] == 0)
        {
            mu[i * pri[j]] = 0;
            break;
        }
        mu[i * pri[j]] = -mu[i];
    }
}

莫比乌斯反演

\(\begin{align*} \sum_{d \mid n} \mu(d) = [n = 1] \end{align*}\)，（太菜了，只会这一种）

• 运用 ：求 \(\begin{align*} \sum_\limits{i = 1} ^ \limits{n} \sum _\limits{j = 1} ^ \limits{m} [\gcd(i,j)=1], (n \le m) \end{align*}\) 的值

  原式

  \(\begin{align*} &=\sum_\limits{i = 1} ^ \limits{n} \sum _\limits{j = 1} ^ \limits{m} \sum _\limits{d \mid (i, j)} \mu(d) \\ &= \sum_\limits{i = 1} ^ \limits{n} \sum _\limits{j = 1} ^ \limits{m} \sum _\limits{d \mid i, d \mid j} \mu(d) \\ &= \sum _ \limits{d = 1} ^ \limits{n} \mu(d) \sum _ \limits{d \mid i} \sum _ \limits{d \mid j} 1 \\ &= \sum _ \limits{d = 1} ^ \limits{n} \mu(d) ( \sum _ \limits{d \mid i} 1 ) (\sum _ \limits {d \mid j} 1), (i \in [1,n], j \in [1, m]) \\ &= \sum _ \limits{d = 1} ^ \limits{n} \mu (d) \lfloor \frac n d \rfloor \lfloor \frac m d \rfloor \end{align*}\)

  然后就可以 \(O(n+n)\) 解决，加上整出分块只需 \(O(n+\sqrt n)\) 即可解决

大佬的莫反blog

整除分块

求 \(\begin{align*} \sum _ \limits{i =1} ^ \limits{n} \lfloor \frac n i \rfloor \end {align*}\) 的值

​ 根据整除商的值呈块状分布，设共有 \(m\) 块，每块的左右端点分别为 \(l_i,r_i,(i\in [1, m] )\) ，则第 \(i\) 块的值为 \(\begin{align*} \lfloor \frac n j \rfloor,j \in [l_i , r_i] \end{align*}\)

​ 则 \(\begin{align*} \sum _ \limits{i =1} ^ \limits{n} \lfloor \frac n i \rfloor = \sum _{i = 1} ^ m (r_i - l_i + 1) \cdot \lfloor \frac n {l_i} \rfloor \end {align*}\)

​ 现在已知第 \(i\) 块的左端点 $l _i $ ，需求右端点 \(r_i\)

​ 根据左端点，可以求得该块的值为 \(\begin{align*} \lfloor \frac n {l_i} \rfloor \end{align*}\)，那么对于 \(\forall j \in [l_i, r_i]\)，都满足 \(\begin{align*} j \cdot \lfloor \frac n {l_i} \rfloor \le n \end{align*}\) ，特别地，当 \(j = r_i\) 时，\(j \mid n\) 且 \(\begin{align*} j \cdot \lfloor \frac n {l_i} \rfloor = n \end{align*}\)

​ 于是可得 \(\begin{align*} r_i = \frac n { \lfloor \frac n {l_i} \rfloor } \end{align*}\)，而 \(l_{i + 1} = r_i + 1\)

​ 由于最多只能分 \(\sqrt n\) 块，每块计算复杂度为 \(O(1)\) ，于是总时间复杂度为 \(O(\sqrt n)\)

int ans = 0;
for (re int l = 1, r; l <= n; l = r + 1)
{
    r = n / (n / l);
    ans = ans + (r - l + 1) * (n / l);
}

神仙的整除分块blog

多项式与生成函数

这个只能请教多项式代师HS了，蒟蒻根本没学懂