注:本文默认 \(n/d\) 为下取整的除法。
整除定义：对于两个数 \(a,b\) ，我们称 \(a|b\) ，当且仅当存在一个 \(k\) 使得 \(b=ak\) 。
这个运算有一些稍微值得被称为性质的性质，如下：
性质1该运算具有传递性，即 \(a|b \and b|c\) 时，\(a|c\) 成立。
好像也没什么好说的性质了。
然后对于 \(a|b\) 的情况下，\(a\) 称为 \(b\) 的约数， \(b\) 称为 \(a\) 的倍数。
实际上所有数之间的关系可以用 \(b=ak+c~(0\le c< a)\) 表示，当 \(c=0\) 时，\(a|b\) 成立。 其中 \(c\) 称为余数。
最大公约数和最小公倍数最大公约数（gcd）和 最小公倍数（lcm） ：字面意思，不多说了。
当 \(\gcd(a,b)=1\) ，那么我们称 \(a,b\) 互素。（多于两个数的情况也有这样类似的定义）
需要注意，多个数互素不一定他们两两互素。
求解gcd如果求解 \(a,b\) 的 \(\gcd(a,b)\) ?
不妨钦定 \(a>b\) 。\(a|b\) 的情况答案直接是 \(a\) ，不考虑了，我们只考虑 \(a\not\mid b\) 的情况。
我们证明 \(\gcd(a,b)=gcd(b,a\%b)\) 成立即可，证明如下：
设 \(a=bk+c\) ，显然有 \(c=a\%b\) 。我们取 \(d\) 满足 \(d|a,d|b\) ，显然 \(d\) 为 \(a,b\) 公约数。
现在我们证明 \(d|c\)：\(c=a-bk\) ，那么 \(c/d=a/d-bk/d\) ，显然 \(c/d\) 为整数，那么 \(d|c\) 。这是必要性。
充分性同理不再赘述。
所以 \(gcd(a,b)=gcd(b,a\%b)\) 成立。Q.E.D.
那么之后递归求解即可。当 \(a\%b=0\) 时，此时的 \(b\) 就是最大公因数。（因为是找到的第一个整除的）
复杂度 \(O(\log n)\) 的。因为每次取模会至少让数折半。
codeint gcd(int x,int y){
if(!x) return y;
return gcd(y%x,x);
}
对于 \(a,b\) 质因数分解得到，\(a=\prod_{i=1}^n p_i^{c_i}\),\(b=\prod_{i=1}^n q_i^{d_i}\)
显然 \(lcm(a,b)=\prod_{i=1}^{n} p_i^{\max\{c_i,d_i\} }\)，\(gcd(a,b)=\prod_{i=1}^{n} p_i^{\min\{c_i,d_i\} }\)
由于 \(c_i+d_i=\max\{c_i,d_i\}+\min\{c_i,d_i\}\)
那么 \(gcd(a,b)lcm(a,b)=ab\) ，可以通过算 \(gcd(a,b)\) 求解。
质数没有除 \(1\) 和它本身以外的因数的数叫做质数。
性质1一个合数 \(n\) 一定存在素数 \(p\le \sqrt n\) 使得 \(p\mid n\) 。
首先合数可以质因数分解且至少有两个质因数，那么结论显然。
性质2所以大于 \(3\) 的质数都可以写成 \(6n\pm 1\) 。
发现 \(6n+2,6n+3,6n+4\) 都不行即可得证。
素数的筛取 欧拉筛
算数基本定理和引理 算数基本引理素数 \(p|ab\) 时，\(p|a\) 和 \(p|b\) 至少成立一个。
质因数分解证明。
算数基本定理对于正整数 \(a\) ，其存在唯一的质因数分解。
证明略证，不为质因数的可以拆成质因数。
同余\(a\equiv b~(mod~n)\) ，字面意思。这样的我们称 \(a\) 与 \(b\) 同余。这个式子称为同余式。
性质1具有传递性。简单不证。
性质2具有线性性和积性。即对于 \(a,b,c,d\in Z,n\in N^*\) ，\(a,b\) 同余， \(c,d\) 同余，那么：
\[a+c\equiv b+d~(mod~n)\\ a\times c\equiv b\times d~(mod~n) \]转成余数大家就都一样了，得证。
性质3对于 \(a,b\in Z,k,m\in N^*\) ，\(a\equiv b~(mod~m)\) ，那么 \(ak\equiv bk~(mod~mk)\)
以及当 \(d|a,d|b,d|m\) 时，\(a/d\equiv b/d~(mod~m/d)\) 成立。
证明：
设 \(a=x_1m+c_1,b=x_2m+c_2\)，那么上述式子只需代入后结论显然。
性质4对于 \(a,b\in Z,d,m\in N^*,d|m\) ，\(a\equiv b~(mod~m)\) ，那么 \(a\equiv b~(mod~d)\)
证明：
设 \(a=x_1m+c_1,b=x_2m+c_2\)，由于 \(d\mid m\) ，\(a\%d=b\%d=c_1=c_2\)
Q.E.D.
同余的乘法逆元然后同余存在乘法逆元的概念。\(ax\equiv 1(mod~b)\)，则 \(x=a^{-1}\) ,称为 \(a\) 的乘法逆元。
逆元的代码
逆元递推式子证明首先 \(1\equiv 1^{-1}(mod~p)\) 显然。
考虑当前求 \(i\) 的逆元。设 \(k=p/i,j=p\%i\) ，有 \(p=ki+j\) ,那么 \(ki+j\equiv 0(mod~p)\)
\[ki+j\equiv 0\\ i^{-1}\equiv -kj^{-1}\\ i^{-1}\equiv -(p/i)(p\%i)^{-1}\\ i^{-1}\equiv p-(p/i)(p\%i)^{-1} \]直接递推即可。
其实我们通过上式中 \((p%i)^{-1}\) 这个部分还可以发现只有当 \(i\not\mid p\) 时，\(i\) 在 \(mod~p\) 意义下才存在逆元。
然后关于另外那些东西为什么正确，我们之后证明。
同余方程形如 \(ax\equiv c(mod~b)\) 的方程叫做同余方程。
扩展欧几里得求解 \(ax+by=gcd(a,b)\) 的算法。
令：
\[ax_1+by_1=gcd(a,b)\\ bx_2+(a\%b)y_2=gcd(b,a\%b) \]则：
\[ax_1+by_1=bx_2+(a\%b)y_2\\ \Leftrightarrow ax_1+by_1=bx_2+(a-((a/b)\times b)~)y2\\\ \Leftrightarrow ax_1+by_1=ay_2+b(x_2-(a/b)y_2) \]于是有 \(x_1=y_2,y_1=x_2-(a/b)y_2\)
递归求解即可。设置 \(x=1,y=0\) 返回递归。
根据一些写法不同，有些细节也不太一样，请注意。
codeint exgcd(int a,int b,int &x,int &y){
if(!a){
x=0;y=1;
return b;
}
int d=exgcd(b%a,a,x,y);
int tmp=y;
y=x;x=tmp-(b/a)*x;
return d;
}
模板题 参考代码：（去除了头文件）
int exgcd(int a,int b,int &x,int &y){
if(!a){
x=0;y=1;
return b;
}
int d=exgcd(b%a,a,x,y);
int tmp=y;
y=x;x=tmp-(b/a)*x;
return d;
}
inline bool LiEu(int a,int b,int c,int &x,int &y){
int d=exgcd(a,b,x,y);
if(c%d) return 0;
int k=c/d;
x*=k;y*=k;
return d;
}
int main(){
filein(a);fileot(a);
int a,b,c=1,x,y;
read(a,b);
if(int d=CgEu(a,b,c,x,y) ){
int t=b/d;
printf("%d\n",(x%t+t)%t);
}
return 0;
}
\(gcd(a,b)\mid c\) 为方程 \(ax+by=c\) 即 \(ax\equiv c(mod~b)\) 有整数解的充要条件。
或者对于正整数 \(a,b\) ，存在 \(x,y\) 使得 \(ax+by=gcd(a,b)\)
证明：
充分性：
设 \(k\) 为最小的非负数满足 \(ax+by=k\)，令 \(q=(a/k)\)
则 \(r=a\%k=a-qk=a-q(ax+by)=a(1-qx)+b(-qy)\)
所以 \(r\) 满足 \(ax+by=r\) ，且 \(r\in[0,k]\)
由于 \(k\) 是满足 \(ax+by=k\) 的最小的正数，有 \(r=0\) ，即 \(k|a\)
同理可得 \(k|b\)
令 \(d=gcd(a,b)\) ，有 \(k|d\) 且 \(k\le d\)
又因为 \(d|a ,d|b\) ，且 \(k=ax+by\) ，得 \(d|k\)
所以 \(d=k\)
所以 \(ax+by=c\) 中 \(c\) 的最小非负取值为 \(\gcd(a,b)\)
显然对于 \(\forall k\gcd(a,b),k\in Z^+\) 都满足 $ax+by=k\gcd(a,b) $
Q.E.D.
必要性：
令 \(d=\gcd(a,b)\)
由 \(ax+by=c\) 有解，\(d|ax,d|by\) ，则 \(d|(ax+by)\)，即 \(d|c\)
Q.E.D.
扩展: 对于关于 \(x\) 的不定方程 \(\sum_{i=1}^n x_iy_i=c\) ，其有解的充要条件是 \(\gcd\{x_i\}|c\)
知道就好，不证了。
我们知道了这个东西，就可以对于方程 \(ax+by=c\) ，先求出 \(x_0,y_0\) 满足 \(ax_0+by_0=gcd(a,b)\) ，那么根据倍数关系直接可以得到一组解 \(x_1=\frac{c}{\gcd(a,b)}x_0,y_1=\frac{c}{\gcd(a,b)}y_0\)
然后我们发现对于 \(x_1,y_1\) ，可知方程的其他解都形如 \(x=x_1+bt,y=y_1-at\)，于是方程所有解都可以求得。
然后 \(x\%t,t=\frac{b}{\gcd(a,b)}\) 就是最小正整数解。
数论函数我们在之前已经稍微提过了，这里不再赘述。
莫比乌斯反演及数论函数基本概念莫比乌斯反演
筛法欧拉筛
杜教筛
欧拉函数定义 \(\varphi(n)\) ，表示小于等于 \(n\) 的数中与 \(n\) 互质的数的个数。
一个显而易见的结论，当 \(n\) 为质数的时候，\(\varphi(n)=n-1\) 。
性质1欧拉函数是积性函数。
结论在 欧拉筛 已经证明。
性质2\(1*\varphi(n)=id(n)\)
证明：
由于函数积性性，所以我们只考虑 \(n=p^c\) 的情况即可。（\(p\) 是质数）
\[1*\varphi(n)=\sum_{d|n}\varphi(\frac{n}{d})\\ =\sum_{i=0}^c \varphi(p^i)\\ =1+p^0(p-1)+p^1(p-1)+...+p^{c-1}(p-1)\\ =p^c=id(n) \]Q.E.D.
性质3设 \(n=\sum_{i=1}^c p_i^{k_i}\)，有 \(\varphi(n)=n\prod_{i=1}^c\frac{p_i-1}{p_i}\)
证明：
\[\varphi(n)=\prod_{i=1}^c\varphi(p_i^{k_i})\\ =\prod_{i=1}^c(p_i-1)\times p_i^{k_i-1}\\ =\prod_{i=1}^c\frac{p_i-1}{p_i}\times p_i^{k_i}\\ =n\prod_{i=1}^c(1-\frac{1}{p_i}) \]Q.E.D.
威尔逊定理（Wilson） 威尔逊定理对于素数 \(p\) 有 \((p-1)!\equiv -1(mod~p)\)
证明这个定理前先证明几个结论。
引理1对于素数 \(p\) 和集合 \(S=\{2,3,4,...,p-2\}\) 中的元素 \(a\)， 一定存在 \(b\in S\) 且 \(a\not=b,b\equiv a^{-1}(mod~p)\)
证明：
反证。
如果 \(b=1\)，且 \(ab\equiv 1(mod~p)\) ，则 \(a\) 必定为 \(1\)，矛盾。
如果 \(b=p-1\) ，则 \(a(p-1)\equiv 1(mod~p)\) ，然后有 \(-a\equiv 1(mod~p)\) ，则 \(a\) 必为 \(p-1\)，矛盾。
因此结论成立。
Q.E.D.
引理2对于元素 \(a\in A\) （\(A,p\) 定义同上），他们模 \(p\) 意义下的逆元互不相同。
证明：
反证。假设存在两个不同的 \(a\) 的逆元 \(a_1,a_2\) ，那么\(a_1a=a_2a=1(mod~p)\) ，则 \((a_1-a_2)a\equiv 1(mod~p)\)，因此 \(a_1=a_2\) ，矛盾。
因此结论成立。
Q.E.D.
接下来证明威尔逊定理。
证明：由引理1，可知 \((p-1)!\Leftrightarrow 1\times(p-1)(mod~p)\)
得证 \((p-1)!\equiv p-1(mod~p)\)
Q.E.D.
费马小定理和欧拉定理 费马小定理若 \(p\) 为素数，则 \(a^{p}\equiv a(mod~p)\) ，如果 \(gcd(a,p)=1\) ，还有 \(a^{p-1}\equiv 1(mod~p)\)
证明：
我们任取一个正整数 \(a\) ，\(a\) 不为 \(p\) 的倍数。
可以发现 \((p-1)!\equiv \prod_{i=1}^{p-1}(i\times a)(mod~p)\)，因为 \(i\times a \%p\) 是互不相同的（相当于增减 \(a\) ，但是由于不整除，余数上固定增减一个小于 \(p\) 的数，又由于模数是素数没有约数必然会错位，所以可知）。
则 \((p-1)!\equiv a^{p-1}\times (p-1)!(mod~p)\)
有 \(a^{p-1}\equiv 1(mod~p)\)
当 \(gcd(a,p)=1\) 不成立时，那个 \(1\) 无法取的，只能得到 \(a^{p}\equiv a(mod~p)\)
欧拉定理若 \(gcd(a,m)=1\) ，则 \(a^{\varphi(m)}\equiv 1(mod~m)\) （注意这里区别在于不需要要求 \(m\) 是素数）
证明：
构造一个与 \(m\) 互质的数列，那么证明就和费马小定理的差不多了。
令 \(n=\varphi(m)\)
设 \(r_1,r_2,...,r_n\) 为一个 \(m\) 的简化剩余系，那么 \(ar_1,ar_2,...，ar_n\) 也是一个 \(m\) 的简化剩余系。
然后有 \(r_1r_2...r_n\equiv a^{n}r_1r_2...r_n(mod~m)\) ，于是 \(a^{\varphi(m)}\equiv 1(mod~m)\)
Q.E.D.
发现费马小定理就是其中一个特殊情况。
扩展欧拉定理 \[a^b= \begin{cases} a^{b\%\varphi(m)},\gcd(a,m)=1\\ a^b,\gcd(a,m)\not=1,b<\varphi(m)\\ a^{b\%\varphi(m)+\varphi(m)},b\ge \varphi(m) \end{cases} ~(mod~m) \]不证啦！想了解的可以看 OI_wiki
中国剩余定理 中国剩余定理求解一元线性同余方程：
\[\begin{cases} x\equiv a_1 (mod~n_1)\\ x\equiv a_2 (mod~n_2)\\ ~~~~\vdots\\ x\equiv a_k (mod~n_k)\\ \end{cases} \]其中 \(n_1,n_2,...,n_k\) 要求互质。
我们提出一种古人的做法，然后证明其正确性并加以理解。
- 计算 \(n=\prod n_i\)
- 对于第 \(i\) 个方程计算 \(m_i=\frac{n}{n_i}\)
- 对于第 \(i\) 个方程计算 \(m_i^{-1}\) （在模 \(n_i\) 意义下）
- 对于第 \(i\) 个方程计算 \(c_i=m_im_i^{-1}\)
- 得出方程唯一解 \(x=\sum_{i=1}^k a_ic_i(mod~n)\)
证明一下这个式子的正确性。
证明：
下面的证明中，第二步的理由是 \(n_i|n\) ，第三步的理由是对于 \(j\not=i\) ，\(m_j\%n_i=0\) 。
\[x\equiv \sum_{j=1}^ka_jc_j(mod~n)\\ \Leftrightarrow x \equiv \sum_{j=1}^ka_jc_j(mod~n_i)\\ \Leftrightarrow x \equiv a_ic_i(mod~n_i)\\ \Leftrightarrow x \equiv a_im_i(m_i^{-1}\%n_i)(mod~n_i)\\ \Leftrightarrow x \equiv a_i(mod~n_i) \]Q.E.D.
codeinline ll CRT(){
ll P=1;
for(int i=1;i<=n;++i) P*=p[i];
for(int i=1;i<=n;++i){
ll zm=P/p[i],fm,y;
LiEu(zm,p[i],1,fm,y);
ans=(ans+1ll*a[i]*zm%P*fm%P)%P;
}
return ans;
}
其实我感觉这个东西和上面的东西没有什么关系了。
先考虑只有两个方程 \(x\equiv a_1(mod~m_1),x\equiv a_2(mod~m_2)\) 的情况。
得到不定方程 \(x=m_1p+a_1=m_2q+a_2\)，即 \(m_1p-m_2q=a_2-a_1\) 。
于是可以 exgcd 求解出一组解 \(p_0,q_0\) 。（当然无解也是可能的）
由于 \(x=m_1p+a_1=m_2q+a_2\)，然后我们构造同余方程 \(x\equiv m_1p+a_1(mod~lcm(m_1,m_2)~)\)
现在我们证明方程的通解是对于其中一个解 \(x_0\) 来说的，有通解 \(x=x_0+klcm(m_1,m_2)\) 。
证明：
等价于证明 \(0,1,2,...,lcm(m_1,m_2)\) 之中只有一个解。
那么我们假设其中有两个解 \(x,y\le lcm(m_1,m_2),x\ge y\) ，那么他们都满足给出的两个方程，相互作差可以发现 \(x-y\) 满足 \((x-y)\% m_1=0\) 和 \((x-y)\%m_2=0\) ，即 \(lcm(m_1,m_2)\mid (x-y)\) 。
由于 \(x,y\le lcm(m_1,m_2)\) ，只有当 \((x-y)=0\) ，即 \(x=y\) 时成立。
那么可知每个模 \(lcm(m_1,m_2)\) 的完全剩余系中只有一组解。
Q.E.D.
因此可得同余方程 \(x\equiv m_1p+a_1(mod~lcm(m_1,m_2)~)\)，多个方程接着以这种方式合并即可。
inline ll mul_low(ll a,ll b,ll p){
ll res=0;bool f=0;
if(b<0) {b=-b;f=1;}
while(b){
if(b&1) res=(res+a+p)%p;
a=(a+a+p)%p;
b>>=1;
}
return f?-res:res;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!a){
x=0;y=1;
return b;
}
ll d=exgcd(b%a,a,x,y);
ll tmp=y;
y=x;x=tmp-(b/a)*x;
return d;
}
inline bool LiEu(ll a,ll b,ll c,ll &x,ll &y){
ll d=exgcd(a,b,x,y);
if(c%d) return 0;
ll k=c/d,t=b/d;
x=mul_low(x,k,t);
return 1;
}
ll a1,a2,m1,m2;
ll gcd(ll a,ll b){
if(!a) return b;
return gcd(b%a,a);
}
inline ll lcm(ll a,ll b){
return (a/gcd(a,b) )*b;
}
int n;
int main(){
filein(a);fileot(a);
read(n);
read(m1,a1);
for(int i=2;i<=n;++i){
read(m2,a2);
ll p,q;
LiEu(m1,m2,a2-a1,p,q);
ll new_m=lcm(m1,m2);
a1=(mul_low(p,m1,new_m)+a1)%new_m;
m1=new_m;
}
printf("%lld\n",a1);
return 0;
}
对于质数 \(p\) ，有：
\[\binom{n}{m}\%p=\binom{n/p}{m/p}\binom{n\%p}{m\%p}\%p \]证明：
发现 \(\binom{p}{n}\%p\) ，只有在 \(n=0\) 或 \(n=p\) 的情况下，有 \(p\not \mid \binom{p}{n}\)。
那么有 \(\binom{p}{n}=[n=0 \or n=p]\)
于是：
\[(a+b)^p\equiv\sum_{i=0}^p\binom{p}{i}a^ib^{p-i}\\ \equiv\sum_{i=0}^p[i=0\or i=p]a^ib^{p-i}\\ \equiv a^p+b^p(mod~p) \]我们由
\[(1+x)^n\equiv\sum_{i=0}^n\binom{n}{i}x^i1^{n-i}\\ \]可知，\(\binom{n}{m}\) 是在第 \(x^m\) 项的取值。
又由我们前面证明的东西：
\[(1+x)^n\equiv(1+x)^{p(n/p)}(1+x)^{n\%p}\\ \equiv(1+x^p)^{n/p}(1+x)^{n\%p} \]然后我们观察第 \(x^m\) 项：
\[\binom{n}{m}x^m\equiv\binom{n/p}{m/p}x^{p(m/p)}\binom{n\%p}{m\%p}x^{m\%p}\\ \equiv\binom{n/p}{m/p}\binom{n\%p}{m\%p}x^{m}\\ \therefore\binom{n}{m}\equiv \binom{n/p}{m/p}\binom{n\%p}{m\%p} (mod~p) \]可以这么构造的原因是 \(p(m/p)\) 必定要是 \(p\) 的倍数，且 \(n\%p\le p-1\) ，所以有且仅有这种构造满足次数和为 \(m\)。
同余最短路大多是两种类型的题目：
- 用很多数拼凑一个大数，问是否可以拼成。
- 给一些数的变换操作（有模数限制），问到达的最少步数。
其中第一个本质上是以一个小数作为模数，展开剩余系，然后对于剩余系上每个数存储最低可以到达的与当前数同余的数，比这个数大或等于就可以到达（因为剩余系的模数是可以用来拼数的），否则到达不了。
第二个本质就是最短路，不过由于模数限制会反复到达一些点。
这个部分不那么需要证明的思想，更多用到的是一种图论感觉的思想。
讲两道典型例题：
跳楼机
题意还是挺简单的，就不再简化了。
本质上就是给了三个数 \(x,y,z\) ，问 \(h\) 及之下有多少可以被拼凑出来。
我们取这个三个数的最小值最为模数展开剩余系，然后形如 \(+k\) 边权为 \(k\) 的边，跑最短路可以得到最低可达。然后计算一下即可。
Small Multiple
题意还是简单，不简化了。
转换一下，对给出的数展开剩余系，可以转换成两种操作：\(\times 10\) 和 \(+1\) 。
可以发现每次 \(+1\) 都使得数位累加 \(+1\) 。我们将这两种操作视作两条边，然后 \(\times 10\) 边权为 \(0\) ，\(+1\) 边权为 \(1\) ，然后从 \(1\) 往 \(0\) 跑最短路。
你可能发现连续 \(+1\) 到进位的情况是不正确的，但是不用担心，这种操作肯定是不优的，因此不会对答案造成影响。
由于最坏一直 \(+1\) 都能到达，复杂度 \(O(n)\) 。
大概就是这样的东西吧。
参考资料数论常见定理 - EricQian06
OI-wiki