数学及数学相关
目录
-
前置知识与符号定义
-
快速幂
-
素数筛
-
裴蜀定理
-
扩展欧几里得算法（exgcd）
-
同余方程
-
费马小定理
-
模意义下的乘法逆元
-
欧拉定理
-
卢卡斯定理
-
中国剩余定理
0.前置知识与符号定义
0.0 缺省源
由于篇幅原因，下文的代码自动省略以下片段：
#include <bits/stdc++.h>
#define int long long
using namespace std;
0.1. 素数
对于一个数 \(p\)，\(p \ne 0,\pm 1\)，且 \(p\) 没有除 \(1\) 与 \(p\) 以外的因数，则认为 \(p\) 是素数，否则认为 \(p\) 是合数。
0.2. 最大公因数
定义 \(\gcd(a,b)\) 为 \(a,b\) 两数的最大公因数，最大公因数是指同时是 \(a,b\) 的因数的数。
0.3. 整除符号
定义 \(d|a\) 表示 \(a\) 可被 \(d\) 整除。
0.4. 模运算
定义 \(a \mod b=a-\lfloor \frac{a}{b} \rfloor \times b\)。
特殊的，当输出一个数 \(k\) 对 \(p\) 取模的结果时，请使用 cout<<(k%p+p)%p 而非 cout<<k%p，这可能导致一些符号错误。
1. 快速幂
对于快速幂的问题定义如下：给定两个整数 \(a,b\)，求 \(a^b \mod k\) 。
对于此类问题，暴力的时间复杂度是显然 \(O(n)\) 的，考虑优化。
我们不妨将指数采用二进制表述，设指数的二进制串为 \(S_{i}\)，\(tmp\) 表示当前二进制位对答案的贡献，\(a\) 表示底数。
若 \(S_{k}=1\)，则 \(ans \gets ans \times tmp\)。由于第 \(k\) 位对答案的贡献为\(a^{2^{k-1}} \times a^{2^{k-1}}\)，即 \(a^{tmp} \times a^{tmp}\)，化简得 \(a^{tmp^2}\) 所以我们在每次操作后使 \(tmp \gets tmp \times tmp\) 即可。
其时间复杂度为 \(O(\log n)\)。
代码：
int m;
int qpow(int a,int b)
{
int ans=1,tmp=a;
while(b!=0)
{
if(b&1)
{
ans=(ans%m*tmp%m)%m;
}
tmp=tmp*tmp%m;
b>>=1;
}
return ans;
}
2. 素数筛
2.1. 埃氏筛
对于素数筛问题的模板题
埃氏筛的思想如下，若我们需要筛出小于等于 \(n\) 的素数，可以枚举 \(2\) 至 \(n\) ，若当前枚举的数 \(k\) 是一个素数，则我们将 \(k\) 的倍数都标志为合数。特殊的，我们不去关心小于 \(k\) 的 \(k\) 倍的数，因为该数在被 \(k\) 考虑之前一定被小于 \(k\) 的数考虑过。
可以证明，其时间复杂度为 \(O(n \log \log n)\)。
以下代码实现筛出 \(n\) 以内的质数：
void prime(int n)
{
int t=0;
for(int i=2;i<=n;i++)
isprime[i]=1;
for(int i=2;i<=n;i++)
{
if(isprime[i])
{
prime[++t]=i;
if(i*i<=n)
for(int j=i*i;j<=n;j+=i)
isprime[j]=0;
}
}
}
2.2.欧拉筛
欧拉筛模板题。
埃氏筛的时间复杂度为 \(O(n \log \log n)\)，无法通过本题。
欧拉筛的时间复杂度为 \(O(n)\)。
对于欧拉筛，每一个数会且仅会被筛到一次。
其做法是对于一个数 \(k\)，遍历当前质数表 \(S\)（\(S\) 呈单调递增），若 \(k \mod S_{i}=0\) 则停止遍历。
容易证明其正确性，若 \(k\mod S_{i}=0\)，则说明 \(S_{i}\) 是 \(k\) 的最小质因数。即 \(S_{i+1}\) 一定不是其最小质因数。那么 \(i\) 乘上 \(S_{k+a}\) 的结果一定会被 \(S_{k}\) 的倍数筛到。
附代码：
void prime(int n)
{
int t=0;
for(int i=2;i<=n;i++)
{
if(!chck[i])
pri[++t]=i;
for(int j=1;i*pri[j]<=n&&j<=t;j++)
{
chck[i*pri[j]]=1;
if(i%pri[j]==0)
break;
}
}
}
3. 裴蜀定理
裴蜀定理的描述如下：
对于整数 \(a,b\)（\(a,b\) 中至少有一个不为 \(0\)），方程 \(ax+by=\gcd(a,b)\) 一定有解。
有以下推论：
-
对于整数 \(a,b\)（\(a,b\) 中至少有一个不为 \(0\)），方程 \(ax+by=d\) ，则 \(d=\gcd(a,b)\)（逆定理）。
-
对于一个数列 \(a\)（\(a\) 中元素不全为 \(0\)）， \(\sum^{n}_{i=1} a_{i}x_{i}=\gcd^n_{i=1}a_{i}\) 一定有解。
该定理证明见 4.3。
4. 扩展欧几里得算法（exgcd）
4.1. 辗转相除法（欧几里得算法）
辗转相除法可以用来求解最大公因数等问题。
其主要算法流程如下：
-
给定两数 \(a,b\)，我们认为 \(a>b\)。
-
若 \(b=0\) 返回 \(a\)。否则递归求解 \(\gcd(b,a \mod b)\)
算法正确性证明如下：
首先证明 \(\gcd(a,b)\) 的答案是 \(gcd(b,a \mod b)\) 的答案。
我们设 \(a=bk+c\)，则 \(\gcd(a,a \mod b)=c\)，设 \(d|a\) 且 \(d|b\) ，则有 \(c=a-bk\)，\(\dfrac{c}{d}=\dfrac{a}{d}-\dfrac{b}{d}k\)。
不难发现 \(\dfrac{c}{d}\) 是整数，即 \(d|c\)，所以 \(\gcd(a,b)\) 的答案是 \(gcd(b,a \mod b)\) 的答案。
逆命题容易证明。
Q.E.D
代码如下：
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
对于两整数 \(a,b\)，有：
在此不做证明。
由此，有：
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
请注意尽量不要使用 <cmath><algorithm> 库中的 __gcd() 函数，这可能导致被卡常。
请注意 <numeric> 库中的 std::gcd 和 std::lcm 仅在 C++ 17 及以上标准中可用，也就是说你在 CCF 的机子上用了就会喜提 CE 0 pts。
4.2 扩展欧几里得算法
4.2.1. exgcd与裴蜀定理
扩展欧几里得算法（exgcd）常用于这样一类问题：给定一个不定方程 \(ax+by=c\)，求其一组合法的整数解，即裴蜀定理。
即：求 \(ax+by=\gcd(a,b)\)，并将求得的 \(x,y\) 分别乘以 \(\dfrac{c}{\gcd(a,b)}\)。
我们可以尝试将问题转化为 4.1 中的欧几里得算法问题，即为 exgcd 算法。
与欧几里得法相似的，我们可以将 \(ax+by=\gcd(a,b)\) 递归为 \(bx'+(a \mod b)y' = \gcd(b,a \mod b)\)
特殊的，exgcd 中 \(ax+by=\gcd(a,b)\) 与 \(bx'+(a \mod b)y' = \gcd(b,a \mod b)\) 并不等价。
由欧几里得算法：
假设 \(bx'+(a \mod b)y ' = \gcd(a,b)\) 中，\(x',y'\) 已知，由模运算定义：
所以
由定义，\(\gcd(a,0)=a\)，此时 \(x=1,y=0\)。
所以我们只需要递归到 \(b=0\) 时终止即可。
于是我们求出了不定方程 \(ax+by=c\) 的一组整数解，这也间接地证明了裴蜀定理。
附代码：
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int h=exgcd(b,a%b,x,y);
int xx=x,yy=y;
x=yy,y=xx-a/b*yy;
return h;
}
4.2.2. exgcd 求不定方程通解
假设我们已经知道了不定方程 \(ax+by=c\) 的一组解 \(x_{0},y_{0}\)，若 \(x_{0}\) 增加 \(r\) 则方程左边增加 \(ar\)，为保证等式成立，\(by\) 需减去 \(ar\)，同时，\(y\) 是整数。这意味着 \(ar\) 是 \(b\) 的倍数。
我们不妨设 \(t=ar\)，因为 \(ar\) 是 \(b\) 的倍数，所以最小的 \(t=\operatorname{lcm}(a,b)\)。
由最小公倍数性质：
带回原式，得：
所以，\(y\)需减去：
所以，不定方程 \(ax+by=c\) 的通解是：
4.2.3 不定方程的无解情况
这与裴蜀定理所讨论的情况不同。
对于不定方程 \(ax+by=c\) 其有解的必要条件是 \(c \bmod \gcd(a,b) = 0\)
证明如下：由最大公因数定义，\(a,b\) 都是 \(\gcd(a,b)\) 的倍数，所以 \(ax+by\) 是 \(\gcd(a,b)\) 的倍数，即 \(c\) 是 \(\gcd(a,b)\) 的倍数。若 \(c \bmod \gcd(a,b) \ne 0\)，与 \(c\) 是 \(\gcd(a,b)\) 的倍数矛盾，不成立。此时不定方程无解。
5. 同余方程
同余方程模板题。
同余方程指的是形如 \(ax \equiv 1 \pmod b\) 的方程。
对于这种方程，我们可以将其转化为上文的不定方程 \(ax+by=c\)。
为什么？
\(a \equiv b \pmod p\) 的本质是 \(a\) 与 \(b\) 之间相差了若干个 \(p\)。
所以\(ax \equiv 1 \pmod b \iff ax+by \equiv 1\)
特殊的，与不定方程类似，同余方程同样可能无解，这发生在 \(a,p\) 不互质的情况，证明如下：
对于不定方程 \(ax+by=1\)，其有解的条件是 \(1 \bmod \gcd(a,b)=0\)，即 \(\gcd(a,b)\) 必须为 \(1\)，即两数互质。
5.1. 同余方程的性质
咕咕咕
6. 费马小定理
费马小定理的描述如下：若 \(p\) 为素数，\(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1 \pmod p\)
费马小定理是欧拉定理的一个推论，将在下文证明其正确性。
7. 模意义下的乘法逆元
所以我们有必要先知道什么是模意义下的乘法逆元（本文不讨论其它逆元，下文逆元皆指“模意义下的乘法逆元”）。
给定二个整数 \(a, p\)，若 \(ax \equiv 1\pmod p\)，则称 \(x\) 是 \(a\) 的逆元。
7.1. exgcd求逆元
逆元模板题。
显然可以用 5. 中提到的同余方程求解。
需要注意的是，由于不定方程可能无解，所以该种求逆元方式只适合 \(a,p\) 互质时。
值得注意的是，这里要求 \(a,p\) 互质，而费马小定理还要求 \(p\) 一定为质数
7.2. 费马小定理求逆元
由费马小定理，\(a^{p-1}\equiv 1 \pmod p\)。
而逆元要求的式子是 \(ax \equiv 1 \pmod p\)。
不难发现 \(x=a^{p-2}\)，快速幂求出即可。
代码如下：
int pow(int a,int p)
{
int poww=p-2;
int pos=a,ans=1;
while(poww)
{
if(poww&1)
ans=ans*pos%p;
pos=pos*pos%p;
poww>>=1;
}
return ans;
}
时间复杂度 \(O(n\log n)\)
7.3. 线性求逆元
todo
8.欧拉定理
我们设 \(\phi(i)\) 为 \(1<=k<=i\) 中与 \(i\) 互质的数的个数。
欧拉定理如下：
可以用一种构造的方式证明其正确性：
wrote on \(Nov.3^{rd},2023\)