##关于整除
###几个有用的性质
- $\displaystyle\left\lfloor\frac{n}{i}\right\rfloor$ 只有 $\sqrt{n}$ 种取值 $,1\leq i \leq n$;
- $\displaystyle\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$ 是 $\displaystyle\left\lfloor\frac{n}{i}\right\rfloor$ 取值相同的一段区间的右端点.
- $\left\lfloor\frac{n}{ab}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{n}{b}\right\rfloor}{a}\right\rfloor\\left\lceil\frac{n}{ab}\right\rceil=\left\lceil\frac{\left\lceil\frac{n}{a}\right\rceil}{b}\right\rceil=\left\lceil\frac{\left\lceil\frac{n}{b}\right\rceil}{a}\right\rceil$
给出正整数 $n,k$ ，计算 $\sum_{i=1}^nk\ mod\ i$.
$1\leq n,k\leq10^9$
对于 $n$ 大于 $k$ 的那一部分，可以直接计算；而剩下的可以分为数个等差数列，运用上述的性质 2 找到右端点后直接等差数列求和即可。
1 |
|
##质数相关
###裴蜀定理 Bezout Theory
- 方程 $ax+by=c$ 有解，当且仅当 $gcd(a,b)\mid c$
###欧几里得算法
时间复杂度 $O(log_2min(a,b))$
1 | int gcd(int a,int b) |
####拓展欧几里得算法
可以在求 $gcd(a,b)$ 的过程中，构造一组 $ax+by=gcd(a,b)$ 的解。
1 | int exgcd(int a,int b,int &x,int &y) |
####二元一次不定方程的通解
令 $d=gcd(a,b)$
求出 $ax+by=c$ 的一组解 $x_0,y_0$ 后，可得到以下形式的方程通解：
- $\displaystyle x=x_0+k\cdot\frac{b}{d}$
- $\displaystyle y=y_0-k\cdot\frac{a}{d}$
####同余方程的解法
对于同余方程 $ax\equiv b\ (\ mod P\ )$
可以化为形如 $ax+Py=b$ 的二元一次不定方程，可用前面的方法求解。
###质数
大于 $1$ 且只被 $1$ 和它本身整除的正整数。
####唯一分解定理（算数基本定理）
- 对于正整数 $n$ ，我们一定可以将其携程若干个质数的幂的乘积的形式，即 $$n=\prod_{i=1}^r p_i^{a_i},p_i\text{ is prime}$$ 且这种分解是唯一的。
####埃拉托斯特尼筛法 Eratosthenes
时间复杂度 $O(Nlog_2log_2N)$
1 | bool notPri[MAXN]; |
####欧拉筛法
时间复杂度 $O(N)$
1 | bool notPri[MAXN]; |
####两次筛法
由于时间复杂度上欧拉筛法要优于埃氏筛，所以我们很少使用埃氏筛法， 但是对于一些比较特殊的问题，埃氏筛还是有其用武之地的。
给定一个区间 $[L,R]$ ，求此区间内两个质数的最小差。
$R-L\leq10^6,R\leq10^{10}$
这样的数据范围显然是不能直接欧拉筛打表的；仔细思考可以发现：虽然 $R$ 可能达到 $10^{10}$ ，但是要筛的区间长度只有 $10^6$ ，需要的质数跨度也只有 $\sqrt R\leq10^5$ ，这些范围是可以接受的， 那么我们考虑先用欧拉筛法筛出 $10^5$ 以下的质数，然后再利用这些质数对 $[L,R]$ 跑埃氏筛即可，时间复杂度 $O((R-L)\log_2\log_2R)$ 。
###威尔逊定理
$p$ 是质数的充要条件为 $\displaystyle(p-1)!\equiv-1\quad(mod\ p)$
求 $$\sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor$$
多组数据， $T\leq10^6,N\leq10^6$
##模逆元
求模逆元的方法有不少，每种各有特点。
通用做法：
###欧拉定理
$$
a^{\varphi(P)}\equiv1\quad(mod\ P)\
a\cdot a^{\varphi(P)}\equiv1\quad(mod\ P)\
a^{-1}\equiv a^{\varphi(P)-1}
$$
时间复杂度 $O(\sqrt{P})$
###拓展欧几里得算法
通过 exgcd 可以求出 $ax+by\equiv1\quad(mod\ b)$ 中 $x,y$ 的一组解；
我们将其替换一下： $a\cdot x+P\cdot y\equiv1\quad(mod\ P)$;
即 $a\cdot x\equiv1\quad(mod\ P)$;
很明显 $a^{-1}=x$.
具体实现：
1 | int exgcd(int a,int b,int &x,int &y) |
时间复杂度 $O(log_2a)$
特殊做法
###费马小定理
若 $a$ 和 $P$ 互质，则 $a^{(P-1)}\equiv1\quad(mod\ P)$
那么 $a^{-1}\equiv a^{(P-2)}\quad(mod\ P)$
可以使用快速幂计算。
1 | typedef long long ll; |
时间复杂度 $O(log_2P)$
###神奇的推导
我们有时候需要在线性复杂度内求出 $[1,n]$ 内所有正整数在模 $P$ 意义下的逆元，这时候我们希望找出一个递推公式。
先把 $P$ 表示为带余除法的形式： $P=ax+b$
则有：
$$
ax+b\equiv0\quad(mod\ P)\
ab^{-1}+x^{-1}\equiv0\quad(mod\ P)\
x^{-1}\equiv-ab^{-1}\quad(mod\ P)\
x^{-1}\equiv\left\lfloor\frac{P}{x}\right\rfloor\cdot(P\ mod \ x)^{-1}\quad(mod\ P)
$$
具体实现：
1 | inv[1]=1; |
时间复杂度 $O(N)$
##余数相关
###剩余系
剩余类
给定 $n$ ，整数按照模 $n$ 取值的不同，可以分为 $n$ 个子集，称为剩余类。
剩余系
给定 $n$ ，从模 $n$ 的 $n$ 个剩余类中各取一个数构成的集合，称为模 $n$ 的一个剩余系，剩余系一般指完全剩余系。
简化剩余系
也称既约剩余系，是模 $n$ 的完全剩余系的一个子集，其中每个元素与 $n$ 互质。
容易验证，简化剩余系中恰好有 $\varphi(n)$ 个元素。（欧拉函数详见后文）
###欧拉定理
若 $(a,n)=1$， 则 $a^{\varphi(n)}\equiv1\quad(mod\ n)$
费马小定理
若 $p$ 是质数且 $(a,p)=1$ ，则 $a^{p-1}\equiv1\quad(mod\ p)$
欧拉定理 EXT
- 若 $(a,p)=1$ ，则 $\displaystyle a^x\equiv a^{x\ mod\ \varphi(p)}\quad(mod\ p)$
- 任何情况下，若 $x>\varphi(p)$ ，则 $\displaystyle a^x\equiv a^{x\ mod\ \varphi(p)+\varphi(p)}\quad(mod\ p)$
###中国剩余定理 CRT
用途：求模线性方程组的解
$$
\begin{cases}
a\equiv B_1(mod\ W_1)\
a\equiv B_2(mod\ W_2)\
\vdots\quad\quad\vdots\quad\quad;,\quad\vdots\
a\equiv B_n(mod\ W_n)\
\end{cases}
$$
1 |
|