基础

更简单的就不说了。

a. 逆元

定义a.1：满足 $ax \equiv 1 \pmod p$ 的 $x$ 称为 $a$ 的逆元

推论a.1.1：当满足 $\gcd(a,p) = 1$ 时，逆元存在。

可用费马小定理或 exgcd 求解。

b. 积性函数

定义b.1：在数论中，若函数 $f(n)$ 满足 $f(1)=1$，且 $f(xy)=f(x)f(y)$ 对任意互质的 $x, y \in\mathbf{N}^*$ 都成立，则 $f(n)$ 为 积性函数。

定义b.2：在数论中，若函数 $f(n)$ 满足 $f(1)=1$ 且 $f(xy)=f(x)f(y)$ 对任意的 $x, y \in\mathbf{N}^*$ 都成立，则 $f(n)$ 为 完全积性函数。

• 常见积性函数：$\varphi,\mu$。

• 完全积性函数：$id(id(n)=n),I(I(n)=1),\epsilon(\epsilon(n)=[n=1])$。

b.1. 性质

• 性质b.1.1：若 $f(x)$ 为积性函数，那么 $f(x^p),f^p(x)$ 也为积性函数。

• 性质b.1.2：若 $f(x),g(x)$ 为积性函数，那么 $f(x)g(x),h(x)=\sum_{d|x}f(x)g(\frac{x}{d})$ 也为积性函数。

c. 迪利克雷卷积

定义c.1：$(f*g)(x)=\sum_{d|x}f(d)g(\frac{x}{d})$

推论c.2：若 $f(x),g(x)$ 为积性函数，那么 $f*g$ 为积性函数。

推论c.2：若 $f(x),g(x)$ 为完全积性函数，那么 $f*g$ 为完全积性函数。

推论c.3：$f*h=g*h \iff f * g$

• $f*\epsilon=f$

• $\mu * I=\epsilon$（莫比乌斯反演）

• $\varphi * I = id$（欧拉反演）

• $\mu * id = \varphi$（综上可证）

道阻且长….

1. 费马小定理&欧拉定理

1.1. 费马小定理

定理1.1.1：当存在整数 $a$ 和质数 $p$ 时，那么： $a^p \equiv a\pmod p$

定理1.1.2：当整数 $a$ 和质数 $p$ 并且 $\gcd(a,p)=1$ 时，那么： $a^{p - 1} \equiv 1\pmod p$

推论1.1.3：$a^{b} \equiv a^{b \bmod (p-1)}\pmod p$。读者自证不难。

证明1.1：oi-wiki.

看下文可以知道，费马小定理是欧拉定理的特殊情况。

1.2. 欧拉定理

定义1.2.1：当 $a, m \in \mathbb{Z}$ ，且 $\operatorname{gcd}(a, m)=1$ 时有：$a^{\varphi(m)} \equiv 1\pmod m$ 。

证明1.2.1：https://zhuanlan.zhihu.com/p/452185813

这里 $\varphi(x)$ 是数论中的欧拉函数。$^{*1}$。

$^{*1}$：详见 4.1。

推论1.2.2：$a^{b} \equiv a^{b \bmod \varphi(m)}\pmod m$。

1.2.4 阶

定义1.2.4.1：若存在最小非负整数$x$满足 $a^x \equiv 1 \pmod m$，则称 $x$ 为 $a$ 模 $m$ 的阶，记为 $\delta_m(a)$。 根据欧拉定理，显然要满足 $\gcd(a,m)=1$。

定理1.2.4.2：$a^x \equiv 1\pmod m$，则$\delta_m(a)|x$。

证明1.2.4.2：设 $x=qd+r$，其中 $0\le r < \delta_m(a)$，由于 $\delta_m(a)$ 最小，所以 $q\ge 1$。所以 $a^r\equiv a^r (a^{\delta_m(a)})^q \equiv a^{q\delta_m(a)+r} \equiv 1 \pmod m$。

于是$r$只能为$0$，得证。

定理1.2.4.3：$a,a^2,...,a^{\delta_m(a)}$ 模 $m$ 意义下两两不同余。

证明1.2.4.3：考虑反证，假设存在两个数 $i \neq j$ ，且 $a^{i} \equiv a^{j}(\bmod m)$ ，则有 $a^{|i-j|} \equiv 1(\bmod m)$ ．但是显然的有：$0<|i-j|<\delta_{m}(a)$，这与阶的最小性矛盾，故原命题成立。

所以当 $a^p\equiv a^q \pmod m$ 时，$p\equiv q \pmod {\delta_m(a)}$。

定理1.2.4.4：$a,b$ 为整数，那么 $\gcd(\delta_m(a),\delta_m(b))=1$ 的充要条件是 $\delta_m(ab)=\delta_m(a)\delta_m(b)$。

证明1.2.4.4：不会。

1.2.5 原根

定义1.2.5.1：满足$\delta_m(a)=\varphi(m)$的$a$，称 $a$ 为模 $m$ 的原根。

原根个数：$\varphi(\varphi(m))$。

原根判定：设 $\varphi(m)$ 的质因数为 $p_1,...p_{s}$，那么 $g$ 是 $m$ 原根的充要条件是：对于任意 $p_i$，满足 $g^{\frac{\varphi(m)}{p_i}}\not\equiv 1 \pmod m$。

证明：充分性显然。必要性不会

$m$ 存在原根，当且仅当 $m=2,4$ 或 $m=p^u,2p^u$，其中 $u$ 为大于 $2$ 的质数。 证明不会。

1.3. 扩展欧拉定理

定义1.3.1：当 $a, m \in \mathbb{Z}$ 时有：

$$a^{b} \equiv\left{\begin{array}{cl} a^{b} & , b<\varphi(m) \ a^{b \bmod \varphi(m)+\varphi(m)} & , b \ge \varphi(m) \end{array}\pmod m \right.$$

2. 裴蜀定理

定义2.1：$p,q$ 非零整数，则对于任意整数 $a,b$ 使得 $\gcd(p,q)|pa+pb$，存在整数 $a,b$ 使得 $pa+pb=\gcd(p,q)$。

推广2.1：多个数也成立。

推论2.2：若 $p,q$ 互质，则存在整数 $a,b$ 使得 $pa+qb=1$。

证明2.2：设 $pa+qb=m$，其中 $m$ 为可能的最小正整数。即证 $m=1\iff m|p,m|q$。

假设不成立，则 $p=nm+r(0<r<m)$，可得 $r=p-nm=p-n(pa+qb)=p(1-na)+q(-nb)$。由于 $1-na,-nb$ 为整数，所以 $r$ 为比 $m$ 更小的正整数，与 $m$ 为可能的最小正整数不符，所以假设不成立，$m=1$。

3. 扩展欧几里得算法

扩展欧几里得算法常用于求 $ax+by=\gcd(a,b)$ 的可行解。

以下是算法原理。

设

$ax_1+by_1=\gcd(a,b)$

$bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)$

由欧拉定理（$\gcd(a,b)=\gcd(b , a \bmod b)$）可得：

$$ax_1+by_1=bx_2+(a\bmod b)y_2$$

根据模的定义转换下，得：

$$ax_1+by_1=bx_2+(a - \lfloor \dfrac{a}{b} \rfloor b)y_2$$

再转换。

$$ax_1+by_1=ay_2+b(x_2- \lfloor \dfrac{a}{b} \rfloor y_2)$$

现在，$x_1,y_1$ 可以通过 $x_2,y_2$ 来求了：

$$\begin{cases} x_1 = y_2 \\ y1 = x_2- \lfloor \dfrac{a}{b} \rfloor y_2 \end{cases}$$

而 $x_2,y_2$ 可以通过 $x_3,y_3$ 来求，而 $x_3,y_3$ 可以通过 $x_4,y_4$ 来求…..

很容易想到，递归。

我们把 $ax \equiv 1 \pmod p$ 转换一下，可得：

$$ax + py = 1$$

用扩展欧几里得算法求出 $x , y$，$x$ 就是 $a$ 在模 $p$ 意义下的逆元。

1
int exgcd(int a , int b){ //返回值是 gcd(a,b)
2
    if(b == 0){
3
        x = 1 , y = 0;
4
        return a;
5
    }
6
    int ret = exgcd(b , a % b);
7
    int tmp = x;
8
    x = y;
9
    y = tmp - (a / b) * y;
10
    return ret;
11
}

1
inline pair <ll , ll> exgcd(ll a , ll b){ //不要gcd返回值
2
    if(b == 0) return make_pair(1 , 0);
3
    pair <ll , ll> ret = exgcd(b , a % b);
4
    return make_pair(ret.second , ret.first - (a / b) * ret.second);
5
}

4. 欧拉函数

4.1定义：对于正整数 $n$。欧拉函数是小于 $n$ 的正整数中与 $n$ 互质的数的个数。表示为 $\varphi(n)$。

其中欧拉函数是积性函数。笔者证明很难。

可以质因数分解来求。

1
inline int phi(int x){
2
    int ret = x;
3
    for(int i = 2;i * i <= x;i++) if(x % i == 0){
4
        ret -= ret / i;
5
        while(x % i == 0) x /= i;
6
    }
7
    if(x > 1) ret -= ret / x;
8
    return x;
9
}

4.2. 性质

• 4.2.1：设 $x = y * p_i$。

  当 $x,y$ 均有质因子 $p_i$ 时，$\varphi(x) = \varphi(y) * p_i$。

  否则 $\varphi(x) = \varphi(y) * (p_i - 1)$。

  证明：

可通过其，用线性筛来求。

1
int ppp[500005] , phi[500005] , cnt;
2
bool vis[10000005];
3
inline void init(){
4
  phi[1] = 1;
5
  for(int i = 2;i <= 10000000;i++){
6
    if(!vis[i]) phi[i] = i - 1 , ppp[++cnt] = i;
7
    for(int j = 1;j <= cnt && i * ppp[j] <= 10000000;j++){
8
      p[i * ppp[j]] = 1;
9
      if(i % ppp[j] == 0){
10
        phi[i * ppp[j]] = phi[i] * ppp[j];
11
        break;
12
      }
13
      phi[i * ppp[j]] = phi[i] * phi[ppp[j]];
14
    }
15
  }
16
}

• 4.2.2：$\gcd(x,y)=1,\varphi(xy)=\varphi(x)\varphi(y)$（积性函数）

• 4.2.3：$\varphi(p^k)=p^{k-1}(p-1)$

• 4.2.4：$\varphi(x)=\displaystyle\prod\varphi(p_i^k)=n\displaystyle\prod\dfrac{p_i-1}{p_i}$

5. 筛法

5.1. 线性筛

$\mathcal O(n)$

1
bool p[N];int ppp[N] , cnt;
2

3
void init(){
4
  for(int i = 2;i <= N;i++){
5
    if(!p[i]) ppp[++cnt] = i;
6
    for(int j = 1;j <= cnt && ppp[j] * i <= N;j++){
7
      p[ppp[j] * i] = 1;
8
      if(i % ppp[j] == 0) break;
9
    }
10
  }
11
}

可以考虑预处理出比 $i$ 小的第一个质数，可以把分解质因数优化成 $O(\log n)$。

1
for(int i = 2;i <= N;i++){
2
  if(!vis[i]) ppp[++cnt] = i , minp[i] = i;
3
  for(int j = 1;j <= cnt && ppp[j] * i <= N;j++){
4
    vis[ppp[j] * i] = 1;
5
    minp[ppp[j] * i] = min(minp[ppp[j]] , minp[i]);
6
    if(i % ppp[j] == 0) break;
7
  }
8
}

积性函数基本可以用线性筛求。

5.2. 埃氏筛

1
void init(){
2
  qwq[1] = 1;
3
  for(int i = 2;i <= n ;i++)
4
    if(!qwq[i])
5
      for(int j = i + i;j <= n;j += i)
6
        qwq[j] = 1;
7
}

5.3. 杜教筛

用于在非线性时间内求积性函数前缀和。

假如求 $S(n) = \sum_{i=1}^n f(i)$。

那么尝试找出一个合适的积性函数 $g$。它们的迪利克雷卷积的前缀和为：

$$\sum_{i=1}^n (f * g)(i)=\sum_{d=1}^n g(d)S(\lfloor \dfrac{n}{d} \rfloor)$$

那么 $g(1)S(n)=\sum_{i=1}^n (f * g)(i)-\sum_{d=2}^n g(d)S(\lfloor \dfrac{n}{d} \rfloor)$。

代码如下：

1
int GetSum(int n) { // 算 f 前缀和的函数
2
  int ans = f_g_sum(n); // 算 f * g 的前缀和
3
  for(int l = 2 , r;l <= n;l = r + 1){
4
    r = n / (n / l);
5
    ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l);// g_sum 是 g 的前缀和
6
  }
7
  return ans;
8
}

复杂度为 $O(n^{\frac{3}{4}})$。

6. 中国剩余定理

常用于求

$$\begin{cases} x\equiv r_1 \pmod {m_1} \ x\equiv r_2 \pmod {m_2} \ … \ x\equiv r_n \pmod {m_n} \ \end{cases}$$

的最小可行解。

6.1. 求解

前提：$m$ 两两互质。

核心思路是把求出 $n$ 个辅助解 $x_i$，每个 $x_i$ 满足：

$$\begin{cases} x_i\equiv 0 \pmod {m_1} \ x_i\equiv 0 \pmod {m_2} \ … \ x_i\equiv 1 \pmod {m_i} \ …\ x_i\equiv 0 \pmod {m_n} \ \end{cases}$$

最后的可行解就是：$\sum r_i x_i$。

现在考虑求出每组 $x_i$。

对于 $x_i$，设 $m_0$ 为可以整除 $x_i$ 的 $m$ 的乘积，于是我们可以知道：$x_i=pm_0=qm_i-1$。

移项得：$qm_i-pm_0=1$。

因为 $m_i,m_0$ 互质，所以有解（裴蜀定理），然后方程可以用扩欧求解，或者看成逆元也行。

1
void exgcd(ll a , ll b){
2
  if(b == 0){
3
    x = 1 , y = 0;
4
    return ;
5
  }
6
  exgcd(b , a % b);
7
  ll tmp = x;
8
  x = y;
9
  y = tmp - (a / b) * y;
10
}
11

12
ll CRT(ll a[15] , ll m[15]){
13
  ll M = 1;
14
  for(int i = 1;i <= n;i++)
15
    M *= m[i];
16
  ll ret = 0;
17
  for(int i = 1;i <= n;i++){
18
    ll mmm = M / m[i];
19
    exgcd(mmm , m[i]);
20
    ll t = (x + m[i]) % m[i];
21
    ret += mmm * t * a[i] % M;
22
    ret %= M;
23
  }
24
  return (ret + M) % M;
25
}

6.2. exCRT

处理 $m$ 不互质的情况。

可以考虑合并两个同余式子。有：

$$\begin{cases} x\equiv r_1 \pmod {m_1} \ x\equiv r_2 \pmod {m_2} \ \end{cases}$$

那么：$x=pm_1+r_1=qm_2+r_2$，移项得 $pm_1-qm_2=r_2-r_1$

令 $d=\gcd(m_1,m_2)$，我们可以用 exgcd 求出方程 $a\frac{m_1}{d}+b\frac{m_2}{d}=\gcd(\frac{m_1}{d},\frac{m_2}{d})=1$ 的一组解，那么：

$$\begin{cases} p=\dfrac{(r_2-r_1)a}{d} \ q=\dfrac{(r_1-r_2)b}{d} \ \end{cases}$$

于是 $x\equiv \dfrac{(r_2-r_1)a}{d} m_1+r_1 \pmod {\text{lcm}(m_1,m_2)}$，然后一个个合并直到剩下一个即可。

1
ll m0 , r0; scanf("%lld%lld" , &m0 , &r0); n--;
2
while(n--){
3
    ll m , r; scanf("%lld%lld" , &m , &r);
4
    ll t = lcm(m0 , m);
5
    ll d = __gcd(m0 , m);
6
    ll x = (exgcd(m0 / d , m / d).first + t) % t;
7
    r0 = (r0 + mul(mul((r - r0) / d , x , t) , m0 , t)) % t;
8
    m0 = t; //mul(a,b,MOD) 慢速乘
9
    r0 = (r0 + m0) % m0;
10
}

7. 反演

7.1. 莫比乌斯函数

定义7.1.1：$\mu(n)=\left\{\begin{array}{c}1, n=1\\0, \exists p, n \equiv 0(\bmod p^2) \\(-1)^{k}(k \text { 是 } n \text { 的质因子个数 })\end{array}\right.$

推论7.1.2：$\sum_{d \mid n} \mu(d)=[n=1] \iff \mu * I=\epsilon$

莫比乌斯函数为积性函数。

7.1.3. 莫比乌斯变换

• 形式a：$f(x)=\sum_{d|n}g(d)$，那么有 $g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$

证明a：已知 $f=g*I$，欲证 $g=f*\mu$ $f*\mu=g*I*\mu=g*\epsilon=g$ 证毕。

• 形式b：$f(x)=\sum_{n|d}g(d)$，那么有 $g(n)=\sum_{n|d}\mu(d)f(\frac{d}{n})$

7.2. 欧拉反演

$n=\sum_{d|n} \varphi(d)$

7.3. 反演技巧

构造函数强行反演：

假如求 $\sum \sum f(\gcd(i,j))$

那么提前求出所有 $f(i)$。

再令 $f(i)=f(i)-\sum_{d|i \& d \not= i} f(d)$

于是 $f(i)=\sum_{d|i} f(d)$。

下面给出模板 $O(n \ln n)$：

1
for(int i = 1;i <= N;i++) f[i] = xx; //预处理f
2
for(int i = 1;i <= N;i++) for(int j = i + i;j <= N;j += i)
3
    f[j] -= f[i];

例题：

P4449 于神之怒加强版

$\sum \sum \gcd(i,j)^k$

那么设 $f(x)=x^k$

所以 $\sum \sum f(\gcd(i,j))$

反演 $\sum \sum \sum_{d|\gcd(i,j)} f(d)$

$\sum_{d=1}^nf(d) \lfloor \dfrac{n}{d}\rfloor \lfloor \dfrac{n}{d}\rfloor$

预处理 $f$ 前缀和，数列分块求解。

扩展：

不是求和怎么办？？

同理

$f(i)=\dfrac{f(i)}{\prod_{d|i \& d \not= i} f(d)}$

于是 $f(i)=\prod_{d|i} f(d)$。

杂项

a. 排列组合

定义a.1：$A_n^m$ 表示从 $n$ 里选 $m$ 个进行排列的方案数。

定义a.2：$A_n^m = \dfrac{n!}{(n - m)!}$

定义a.3：$C_n^m$ 表示从 $n$ 中选 $m$ 个（不考虑顺序）的方案数。

定义a.4：$C_n^m = \dfrac{A_n^m}{A_m^m} = \dfrac{n!}{m!(n - m)!}$

推论a.5：$C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1}$。不难发现，此乃杨辉三角。

理论到实际

zbj 问题

每个数值域为 $[1,m]$，$n$ 个数单增的数量为 $C_m^n$ 不降的是 $C_{n+m-1}^{n-1}$。

$n$ 个 zbj 放到 $m$ 个箱子中，每个箱子至少一个，$C_{n - 1}^{m-1}$。

$n$ 个 zbj 放到 $m$ 个箱子中，可以先每个箱子放一个，所以$C_{n+m-1}^{m-1}$。

数论分块

用于求 $\displaystyle\sum_{i=1}^{n} \lfloor \dfrac{n}{i}\rfloor$

1
for(int l = 1 , r;l <= n;l = r + 1){
2
  r = n / (n / l);
3
  ret += (r - l + 1) * (n / l);
4
}

斐波那契数列

定义

$$F_0=0,F_1=1$$

$$F_n=F_{n-1}+F_{n-2} \tag{1}$$

$$F_n=\dfrac{1}{\sqrt{5}}\bigg[\bigg(\dfrac{1+\sqrt{5}}{2}\bigg)^n - \bigg(\dfrac{1-\sqrt{5}}{2}\bigg)^n \bigg]$$

推导

设

$$F_n-\lambda F_{n-1}=\mu(F_{n-1}-\lambda F_{n-2}) \tag{2}$$

$$F_n=(\mu+\lambda) F_{n-1}-\mu\lambda F_{n-2}$$

根据 $(1)$ 得：

$$\begin{cases} \mu+\lambda&=1 \ \mu \lambda&=-1 \end{cases}$$

解得：

$$\begin{cases} \mu=\frac{1+\sqrt{5}}{2} \ \lambda=\frac{1-\sqrt{5}}{2} \end{cases} \quad or \quad \begin{cases} \mu=\frac{1-\sqrt{5}}{2} \ \lambda=\frac{1+\sqrt{5}}{2} \end{cases}$$

分别带回 $(2)$：

$$\begin{cases} F_n-\frac{1-\sqrt{5}}{2} F_{n-1}=\frac{1+\sqrt{5}}{2}(F_{n-1}-\frac{1-\sqrt{5}}{2} F_{n-2})\ F_n-\frac{1+\sqrt{5}}{2} F_{n-1}=\frac{1-\sqrt{5}}{2}(F_{n-1}-\frac{1+\sqrt{5}}{2} F_{n-2}) \end{cases}$$

显然数列 $\{F_n-\lambda F_{n-1}\}$ 为等比数列，公差为 $\frac{1+\sqrt{5}}{2}$ 或 $\frac{1-\sqrt{5}}{2}$。则：

$$\begin{cases} F_n-\frac{1-\sqrt{5}}{2} F_{n-1} =\bigg(F_2-\frac{1-\sqrt{5}}{2} F_{1}\bigg)\bigg(\dfrac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad&(3) \ F_n-\frac{1+\sqrt{5}}{2} F_{n-1} =\bigg(F_2-\frac{1+\sqrt{5}}{2} F_{1}\bigg)\bigg(\dfrac{1-\sqrt{5}}{2}\bigg)^{n-1} \quad&(4) \end{cases}$$

然后

$$\dfrac{1+\sqrt{5}}{2} \times (3)-\dfrac{1-\sqrt{5}}{2} \times (4)$$

得

$$\sqrt{5}F_n=\bigg(\dfrac{1+\sqrt{5}}{2}\bigg)^{n}-\bigg(\dfrac{1-\sqrt{5}}{2}\bigg)^{n}$$

$$F_n=\dfrac{1}{\sqrt{5}}\bigg[\bigg(\dfrac{1+\sqrt{5}}{2}\bigg)^{n}-\bigg(\dfrac{1-\sqrt{5}}{2}\bigg)^{n}\bigg]$$

性质

由上可以发现：

$$\begin{cases} \mu=\frac{1}{\phi}=\frac{1+\sqrt{5}}{2} \ \lambda=\phi=\frac{1-\sqrt{5}}{2} \end{cases} \quad or \quad \begin{cases} \mu=\phi=\frac{1-\sqrt{5}}{2} \ \lambda=\frac{1}{\phi}=\frac{1+\sqrt{5}}{2} \end{cases}$$

（$\phi$ 指黄金分割比 $\dfrac{\sqrt{5}-1}{2}$）

所以通项公式可以写成：

$$F_n=\dfrac{1}{\sqrt{5}}\bigg(\phi^{-n}-\phi^{n}\bigg)$$

时间复杂度相关

代换法

$T(n)=2T(\lfloor \frac{n}{2} \rfloor)+n$

直觉

$$T(n)\le c n \log_2 n$$

所以

$$T(\lfloor \frac{n}{2} \rfloor)\le c \lfloor \frac{n}{2} \rfloor \log_2 \lfloor \frac{n}{2} \rfloor$$

带回原式

$$T(n)\le 2c \lfloor \frac{n}{2} \rfloor \log_2 \lfloor \frac{n}{2} \rfloor+n\le cn \log_2 \frac{n}{2} +n\ =cn\log_2 n - cn + n \le cn\log_2 n$$

$c\ge 1$ 时成立。

主公式

内容

证明

小公式

$(a+b)^3 =(a^2+ab)(a+b)+(ab+b^2)(a+b)=a^3+b^3+3a^2b+3ab^2$

$(a-b)^3 =a^3-b^3-3a^2b+3ab^2$

$a^3+b^3=(a+b)(a^2-ab+b^2)$

$a^3-b^3=(a-b)(a^2+ab+b^2)$

$(a+b)^n = \displaystyle\sum_{k = 0}^nC^n_kx^{n-k}y^k = \displaystyle\sum_{k = 0}^nC^n_k x^{k}y^{n-k}$

$\displaystyle\sum_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}$

$\displaystyle\sum_{i=1}^n i^3=\dfrac{(n + 1)^2n^2}{4}$

当 $n$ 是正奇数时

$a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2-...-ab^{n-2}+b^{n-1})$

对于 $f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$

当 $f(c)=0$ 时，设有理数根 $c=\dfrac{p}{q}$（$p,q$ 互质）。

$x-c$ 除 $f(x)$ 时，余数是 $f(c)$。