1.整除和同余
1.1 整除
1.1.1 定义
\(\text{如果有}a,b,c\in N,\text{且}b=a\times c,\text{则称}a\text{整除}b,\text{记作}a\mid b\)
1.1.2 性质
-
\(a\mid a\)
-
若 \(a\mid b\) 且 \(b\mid c\),则 \(a\mid c\)
-
若 \(a\mid b_1,a\mid b_2,\cdots,a\mid b_n\)，则 \(a\mid b_i\times c_i(i\in \left[1,n\right])\) 且 \(a\mid \sum\limits^n_{i=1} (b_i\times c_i)\)
-
若 \(a\mid b\) 且 \(a\mid b\pm c\)，则 \(a\mid c\)
-
若 \(n\mid a-b\) 且 \(n\mid c-d\),则 \(n\mid a\times c-b\times d\)
1.2 同余
1.2.1 定义
\(\text{如果有}a,b,n\in N,n\mid a-b,\text{则称}a\text{与}b\text{模}n\text{同余},\text{记作}a\equiv b\pmod n\)
1.2.2 性质
\(\begin{aligned} &1.a\equiv a\pmod n\cr\cr &2.\text{若}a\equiv b\pmod n,\text{则}b \equiv a\pmod n\cr\cr &3.\text{若}a\equiv b\pmod n\text{且}b\equiv c\pmod n,\text{则}a\equiv c\pmod n\cr\cr &4.\text{若}a\equiv c\pmod n\text{且}b\equiv d\pmod n,\text{则}a+b\equiv c+d\pmod n\text{且}a\times b\equiv c\times d\pmod n\cr\cr &5.\text{若}a\equiv b\pmod n,\text{则}a\times c\equiv b\times c\pmod n\cr\cr &\ \ \ \text{反之若}a\times c\equiv b\times c\pmod n\text{且}c \not=0,\text{则}a\equiv b\pmod n \end{aligned}\)
1.2.3 完全剩余系
\(\text{若一个整数数列}a_1,a_2,\cdots ,a_n\text{除以}n\text{的余数两两不同},\text{则称为一个模}n\text{的完全剩余系}\)
2.约数和倍数
2.1 约数
2.1.1 定义
\(\text{若}d \mid n,\text{则称}d\text{是}n\text{的约数},n\text{是}d\text{的倍数}\)
2.1.2 某个数的约数
\(\text{试除法：}\)
ull factor[size];
void find_factor(ull n) {
ull sq = 1ll*sqrt(n+0.5);
for(ull i = 1;i <= sq;++i)
if(n%i == 0) {
factor[++factor[0]] = i;
if(i != n/i)
factor[++factor[0]] = n/i;
}
return;
}
2.1.3 区间内数的约数
vector<ull> factor[size];
void find_factor(ull n) {
for(ull i = 1;i <= n;++i)
for(ull j = 1;j <= n/i;++j)
factor[i*j].push_back(i);
return;
}
2.2 最大公约数
2.2.1 定义
\(\text{一个整数数列}a_1,a_2,\cdots,a_n\text{的最大公约数}(\text{记作}\gcd(a_1,a_2,\cdots,a_n))\)
\(\text{就是同时整除}a_1,a_2,\cdots,a_n\text{的最大整数}\)
2.2.2 裴蜀定理
\(\begin{aligned} &1.\text{对任何}a_1,a_2,\cdots,a_n\in N,\text{存在}x_1,x_2,\cdots,x_n,\cr\cr &\ \ \ \text{使得}\gcd(a_1,a_2,\cdots,a_n)=a_1\times x_1+a_2\times x_2+\cdots+a_n\times x_n\cr\cr &2.\text{推论：}a_1,a_2,\cdots,a_n\in N,a\in N_+,\cr\cr &\ \ \ \text{则}\gcd(a\times x_1,a\times x_2,\cdots,a\times x_n)=a\times\gcd(x_1,x_2,\cdots,x_n)\cr\cr &3.\text{同时：}\gcd(a_1,a_2,\cdots,a_n)=\gcd(\gcd(a_1,a_2,\cdots,a_{n-1}),a_n)\cr\cr &4.\text{又可得：若}a\div b=q\cdots\cdots r,\text{则}\gcd(a,b)=\gcd(b,r) \end{aligned}\)
2.2.3 欧几里得方法
\(\text{其实上面的第四条已经离欧几里得方法很近了},\text{因为}\gcd(a,b)=\gcd(b,a\%b)\)
\(\text{递归去求即可:}\)
int gcd(int a,int b) {
return b == 0 ? a : gcd(b,a%b);
}
\(\text{当然也可以循环去求:}\)
int gcd(int x,int y) {
int r = x%y;
while(r) {
x = y;
y = r;
r = x%y;
}
return y;
}
2.2.4 互质
\(\text{如果两个数}a,b\in N,\gcd(a,b)=1,\text{则称}a,b\text{互质}\)
2.2.5 模n逆
\(\text{若}\gcd(a,b)=1,\text{则}\exists x\in N,\text{使得}x\times a\equiv 1\pmod b\)
\(\text{反之任意满足条件的}x\in N \text{模}b\text{同余}\)
2.2.6 高斯引理
\(\text{若}a\mid b\times c,\gcd(a,b)=1,\text{则}a\mid c\)
\(\text{若}\gcd(a,n)=\gcd(b,n)=\gcd(c,n)=1,\text{且}a\times b\equiv a\times c\pmod n,\text{则}b\equiv c\pmod n\)
2.3 最小公倍数
2.3.1 定义
\(\text{若有一个整数数列}a_1,a_2,\cdots,a_n\text{，则它们的最小公倍数}(\text{记作}\operatorname{lcm}(a_1,a_2,\cdots,a_n))\)
\(\text{为同时被}a_1,a_2,\cdots,a_n\text{整除的最小整数}\)
2.3.2 性质
\(\begin{aligned} &1.\operatorname{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}\cr\cr &2.\operatorname{lcm}(a_1,a_2,\cdots,a_n)=\operatorname{lcm}(\operatorname{lcm}(a_1,a_2,\cdots,a_{n-1}),a_n)\cr\cr &3.\operatorname{lcm}(a,b)\ge\dfrac{a\times b}{b-a}(b>a)\cr\cr &4.\text{若}\dfrac{\operatorname{lcm}(a,b)}{\gcd(a,b)}=a-b,\text{则}\operatorname{lcm}(a,b)={\gcd}^2(a,b)\cr\cr &5.\text{若}\operatorname{lcm}(x,y)-\operatorname{lcm}(x,z)=y-z,\text{则}x\mid y, x\mid z \end{aligned}\)
\(\text{其中我们通过性质1可得到求解最小公倍数的方法}\)
int lcm(int a,int b) {
return a*b/gcd(a,b);
}
3.质数和合数
3.1 质数
3.1.1 定义
\(\text{若}p\in N_+\text{无法被除了}1\text{和它本身以外的任何自然数整除},\text{则称}p\text{为质数}\)
3.1.2 试除法
\(\text{根据定义，我们可以通过试除小于}n\text{的每一个整数来判断}n\text{是否为质数}\)
\(\text{实际上我们只用用}\left(1,\sqrt n\right]\text{试除即可}\)
bool isPrime(long long aim) {
if(aim == 1) return false;
if(aim == 2) return true;
long long sq = 1ll*sqrt(aim+0.5);
for(long long i = 2;i <= sq;++i)
if(aim%i == 0) return false;
return true;
}
\(\text{时间复杂度就是}O(\sqrt n)\)
3.1.3 Miller-Rabin素性测试
\(\text{这种方法适用于快速对一个数是否为质数的问题作出判断，并要求保证较高的正确性}\)
\(\text{虽然但是，它的正确性不是1}\)
bool Miller_Rabin(ull aim) {
if(aim == 2) return true;
if(aim < 2||!(aim&1)) return false;
ull tmp = aim-1, temp = 0;
while(!(tmp&1)) {
temp++;
tmp >>= 1;
}
int check_times = 20;
for(int outs = 1;outs <= check_times;++outs) {
ull a = rand()%(aim-1)+1, x = turtle_pow(a,tmp,aim), y;
for(int i = 1;i <= temp;++i) {
y = turtle_mul(x,x,aim);
if(y == 1&&x != 1&&x != aim-1)
return false;
x = y;
}
if(y != 1) return false;
}
return true;
}
\(\text{时间复杂度是}O(\log(n))\)
3.1.4 线性筛素数
int prime[the_size];
bool check[the_size];
void linePrime(int n) {
check[0] = check[1] = true;
for(int i = 2;i <= n;++i) {
if(!check[i])
prime[++prime[0]] = i;
for(int j = 1;j <= prime[0];++j) {
if(i*prime[j] > n) break;
check[i*prime[j]] = true;
if(i%prime[j] == 0) break;
}
}
}
3.1.5 既约剩余系
\(\text{若一个整数数列}a_1,a_2,\cdots ,a_k\text{使得任何与}n\text{互素的整数总是模}n\text{同余于}a_1,a_2,\cdots ,a_k\text{中的一个},\)
\(\text{则称}a_1,a_2,\cdots ,a_k\text{为}n\text{的既约剩余系}\)
3.2 合数
3.2.1 定义
\(\text{很明显},\text{若}n\in N_+\text{不是质数},\text{则它是合数}\)
3.3 质数的无限性
3.3.1 证明
\(\text{假设只有有限个素数}p_1,p_2,\cdots,p_k.\)
\(\text{考虑}p_1\times p_2\times \cdots\times p_k+1,\text{取它的一个质因子}q.\)
\(\text{则}q\in\{p_1,p_2,\cdots,p_k\},\text{又}q\mid p_1\times p_2\times\cdots\times p_k+1,\text{所以}q\mid 1.\text{矛盾}\)
3.4 基本算术定理
3.4.1 证明
\(\text{基本算术定理的内容是：}\)
\(\text{任何一个大于}1\text{的正整数都能被唯一分解成有限个质数的乘积，可记作：}\)
\[n={p_1}^{\alpha_1}\times{p_2}^{\alpha_2}\times\cdots\times{p_k}^{\alpha_k} \]\(\text{让我们从一个弱形式开始：}\)
\[\text{任何大于}1\text{的}n\in N\text{都可以写成素数的乘积} \]\(\text{证明：}\)
3.4.2 质因数分解
\(\text{还是试除法：}\)
vector<ull> pf, times;
void prime_divide(ull n) {
ull sq = 1ll*sqrt(n+0.5);
for(ull i = 2;i <= sq;++i)
if(n%i == 0) {
pf.push_back(i);
times.push_back(1);
n /= i;
while(n%i == 0) {
times[times.size()-1]++;
n /= i;
}
}
if(n > 1) {
pf.push_back(n);
times.push_back(1);
}
}
4.威尔逊定理
4.1 内容与证明
4.1.1 威尔逊定理
\(\text{威尔逊定理的内容是：}p\in N\text{为质数等价于}(p-1)!+1\equiv 0\pmod p\)
4.1.2 证明
\(\begin{aligned} 1.&\text{充分性：对}x\in\{1,2,\cdots,p-1\},\text{设}inv_x\times x\equiv 1\pmod p.\cr\cr &\text{现将}\{1,2,\cdots,p-1\}\text{分组},\text{若}inv_x\not=x,inv_x\text{和}x\text{一组};\text{否则}x\text{单独一组}.\cr\cr &\text{成对的}inv_x\times x\equiv 1\pmod p,\text{不成对的数}x^2\equiv 1\pmod p.\cr\cr &\text{等价于}(x-1)\times(x+1)\equiv 0\pmod p,\text{其解恰为}1\text{和}-1.\cr\cr &\text{因此}(p-1)!=1\times2\times\cdots\times(p-1)\bmod p\text{同余于不成对的数的乘积},\text{即}-1.\cr\cr 2.&\text{必要性：设}n\text{是合数},\text{记}n=a\times b\ (a,b>1),\text{则}a\times b-1\ge a.\cr\cr &\text{因此}a\mid (n-1)!,\text{与}a\mid (n-1)!+1\text{矛盾},\text{故}n\text{是质数}. \end{aligned}\)
5.丢番图方程
5.1 线性丢番图方程
\(\text{一个最简单的线性同余方程形如：}\)
\[a_1\times x_1+a_2\times x_2+\cdots+a_k\times x_k=b \]5.1.1 解
\(1.\text{方程}a_1\times x_1+a_2\times x_2+\cdots+a_k\times x_k=b\text{有解},\text{等价于}\gcd(a_1,a_2,\cdots,a_k)\mid b\)
\(2.\text{若方程}a\times x+b\times y=c\text{有一特解}(x_0,y_0),\)
\(\text{则有通解}(x_0+\dfrac{b}{\gcd(a,b)}\times t,y_0+\dfrac{b}{\gcd(a,b)}\times t)\ (t\in Z)\)
5.1.2 扩展欧几里得方法
\(\text{扩展欧几里得用来解决这样一个特殊的同余方程：}a\times x+b\times y=\gcd(a,b)\)
\(\text{其中}a,b\text{已知}\)
ull ex_gcd(ull a,ull b,ull &x,ull &y) {
if(b == 0) {
x = 1, y = 0;
return a;
}
ull res = ex_gcd(b,a%b,x,y);
ull tmp = x;
x = y;
y = tmp-a/b*y;
return res;
}
\(\text{设解为}(x_0,y_0),\text{则方程}a\times x+b\times y=c\text{的一组特解为}(\dfrac{c}{\gcd(a,b)}\times x_0,\dfrac{c}{\gcd(a,b)}\times y_0)\)
6.排列与组合
6.1 加法原理
6.2 乘法原理
6.3 排列数
6.4 组合数
6.5 二项式定理
7.数论函数
7.1 常见数论函数
7.1.1 常见数论函数
\(\begin{aligned} &\varphi(n):\left[1,n\right]\text{中与}n\text{互质的数的个数}\cr\cr &\tau(n):n\text{的正因子个数}\cr\cr &\sigma(n):n\text{的正因子之和}\cr\cr &\omega(n):n\text{的不同质因子的个数}\cr\cr &\Omega(n):n\text{的质因子的个数}\cr\cr &\pi(n):\left[1,n\right]\text{中的质数的个数}\cr\cr &\mu(n)=\begin{cases} (-1)^{\omega(n)}&\omega(n)=\Omega(n)\\ 0&\omega(n)\not=\Omega(n)\\ \end{cases}\cr\cr &\nu_p(n):n\text{的质分解中}p\text{的幂次}\cr\cr &\gamma_k(n):\text{满足}n={x_1}^2+{x_2}^2+\cdots+{x_k}^2\text{的数组}{x_1,x_2,\cdots,x_k}\text{的个数} \end{aligned}\)
7.2 数论卷积
7.3 积性函数
7.4 欧拉函数
7.4.1 性质
\(\text{设}n\text{的质因子分解式为}{p_1}^{\alpha_1}\times{p_2}^{\alpha_2}\times\cdots\times{p_k}^{\alpha_k}\)
\(\begin{aligned} &1.\varphi(n)=\prod\limits_{i=1}^{k}({p_i}^{\alpha_i-1}\times(p_i-1))\cr &\ \ \ \varphi(n)=n\times\prod\limits_{i=1}^{k}(1-\dfrac{1}{p_i})\cr\cr &2.\text{若}\gcd(n,m)=1,\text{则}\varphi(m\times n)=\varphi(n)\times\varphi(m)\cr &\ \ \ \text{若}a\mid b,\text{则}\varphi(a)\mid\varphi(b)\cr\cr &3.\sum\limits_{i=1}^{n}(\varphi(i)\times\left\lfloor\dfrac{n}{i}\right\rfloor)=\dfrac{n\times(n+1)}{2}\cr\cr &4.\sum\limits_{d\mid n}\varphi(d)=n\cr\cr &5.\text{若}d\mid n,\text{则}\left[1,n\right]\text{中与}n\text{的最大公约数为}d\text{的个数有}\varphi(\tfrac{n}{d})\text{个} \end{aligned}\)
7.4.2 求法
\(\text{利用上文的性质}1\text{我们可以求解}\varphi(n)\)
ull EulerFunction(ull aim) {
ull sq = 1ll*sqrt(aim+0.5);
ull ans = aim;
for(ull i = 2;i <= sq;++i)
if(aim%i == 0) {
ans = ans/i*(i-1);
while(!(aim%i))
aim /= i;
}
if(aim > 1) ans = ans/aim*(aim-1);
return ans;
}
7.4.3 线性求法
ull primeLine[z];
bool primeIs[z] = {1,1};
ull phiLine[z];
void linePhi(ull n) {
phiLine[1] = 1;
for(ull i = 2;i <= n;++i) {
if(!primeIs[i]) {
primeLine[++primeLine[0]] = i;
phiLine[i] = i-1;
}
for(int j = 1;j <= primeLine[0]&&i*primeLine[j] <= n;++j) {
primeIs[i*primeLine[j]] = true;
if(!(i%primeLine[j])) {
phiLine[i*primeLine[j]] = primeLine[j]*phiLine[i];
break;
} else {
phiLine[i*primeLine[j]] = (primeLine[j]-1)*phiLine[i];
}
}
}
}
7.5 莫比乌斯函数
7.5.1 性质
\(\text{莫比乌斯函数的一个重要性质是：}\sum\limits_{d\mid n}\mu(d)=\delta_{1,n}\)
\(\text{注}:\delta_{a,b}=\begin{cases}1&a=b\\0&a\not=b\\\end{cases}\)
$ n=1\text{显然},$
7.5.2 莫比乌斯反演
\(\text{接下来我们来证明莫比乌斯反演}:\)
\(\text{若}f(n)=\sum\limits_{d\mid n}g(d),\text{则}g(n)=\sum\limits_{d\mid n}(\mu(\tfrac{n}{d})\times f(d))\)
\(\begin{aligned}\sum\limits_{d\mid n}(\mu(\tfrac{n}{d})\times f(d))=\sum\limits_{d\mid n}(\mu(\tfrac{n}{d})\times\sum\limits_{e\mid d}g(e)\end{aligned}\)
\(\ \ \begin{aligned} &=\sum\limits_{e\mid n}(g(e)\times\sum\limits_{e\mid d\mid n}\mu(\tfrac{n}{d}))\cr &\text{记}d = e\times x\cr &=\sum\limits_{e\mid n}(g(e)\times\sum\limits_{x\mid\tfrac{n}{e}}\mu(\frac{\tfrac{n}{e}}{x}))\cr &=\sum\limits_{e\mid n}(g(e)\times\delta_{1,\tfrac{n}{e}})\cr &=g(n) \end{aligned}\)
\(\text{它还有乘积形式：}\)
\(\text{若}f(n)=\prod\limits_{d\mid n}g(d),\text{则}g(n)=\prod\limits_{d\mid n}{f(d)}^{\mu(\tfrac{n}{d})}\)
7.5.3 无平方因子数
\(\text{我们定义}Q(n)\text{为}\left[1,n\right]\text{中的无平方因子数的个数},\text{则：}\)
\[Q(n)=\sum\limits_{k\le\sqrt n}(\mu(k)\times\left\lfloor\frac{n}{k^2}\right\rfloor) \]8.费马小定理和欧拉定理
8.1 费马小定理
\[\text{对于素数}p\text{和正整数}a,\text{有}a^p\equiv a\pmod p \]8.1.2 证明
8.1.3 一些推论
8.2 欧拉定理
\[\text{若}a,n\in N_+,\gcd(a,n)=1,\text{则}a^{\varphi(n)}\equiv 1\pmod n \]8.3 扩展欧拉定理
\[ a^b=\begin{cases} a^{b \bmod \varphi(n)}&gcd(a,n)=1\\ a^b&gcd(a,n)\not=1,b < \varphi(n)\pmod m\\ a^{(b\bmod \varphi(n))+\varphi(n)}&gcd(a,n)\not=1,b\ge\varphi(n)\\ \end{cases}\]9.乘法逆元
9.1 费马小定理
\(\text{由费马小定理可得：}a\text{在模质数}p\text{意义下的逆元为}a^{p-2}\)
ull quick_pow(ull a,ull n,ull p) {
ull res = 1;
a %= p;
while(n) {
if(n&1) res = res*a%p;
a = a*a%p;
n >>= 1;
}
return res;
}
ull p_inv(ull a,ull p) {
return quick_pow(a,p-2,p);
}
9.2 欧拉定理
\(\text{有欧拉定理可得：若}\gcd(a,n)=1\text{则}a\text{在模}n\text{意义下的逆元为}a^{\varphi(n)-1}\)
\(\text{我们不用担心这种方法求逆元会受到限制，因为如果}\gcd(a,n)\not=1,\)
\(\text{则不存在}a\text{模}n\text{意义下的逆元}\)
9.3 扩展欧几里得
\(\text{由于}a\text{在模}n\text{意义下的逆元}x\text{满足}a\times x\equiv1\pmod n\)
\(\text{所以有方程}a\times x+n\times y=1,\text{根据逆元性质},\gcd(a,n)=1,\)
\(\text{所以解方程}a\times x+n\times y=\gcd(a,n)\text{即可}\)
ull ex_gcd(ull a,ull b,ull &x,ull &y) {
if(!b) {
x = 1, y = 0;
return a;
}
ull res = ex_gcd(b,a%b,x,y);
ull tmp = x;
x = y;
y = tmp-a/b*y;
return res;
}
ull gcd_inv(ull a,ull p) {
ull x, y;
ull tmp = ex_gcd(a,p,x,y);
if(tmp != 1) return -1;
return ((x%p)+p)%p;
}
9.4 线性求逆元
ull inv[size];
void line_inv(ull n,ull p) {
inv[1] = 1;
for(ull i = 2;i <= n;++i)
inv[i] = 1ll*(p-p/i)*inv[p%i]%p;
return;
}
10.中国剩余定理
10.1 中国剩余定理
\(\text{我们现在有一个同余方程组如下}:\)
\(\begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \vdots\\ x\equiv a_n\pmod{m_n}\\ \end{cases}\)
\(\text{其中}m_1,m_2,\cdots,m_n\text{两两互质}\)
\(\text{那么设}M = \prod\limits_{i=1}^{n}m_i,M_i=\dfrac{M}{m_i},inv_i\text{为}M_i\text{在模}m_i\text{意义下的逆元}\)
\(\text{则方程组有一特解为}x_0=\sum\limits_{i=1}^{n}(M_i\times a_i\times inv_i)\)
\(\text{同时这个方程的通解为}x=x_0+k\times M(M\in Z)\)
\(\text{此时我们就可以通过算乘法逆元来求解此同余方程组了}\)
ull ex_gcd(ull a,ull b,ull &x,ull &y) {
if(!b) {
x = 1, y = 0;
return a;
}
ull res = ex_gcd(b,a%b,x,y);
ull tmp = x;
x = y;
y = tmp-a/b*y;
return res;
}
ull CRT(const ull n,ull *m,ull *a) {
ull M = 1, Mi, x, y, res = 0;
for(int i = 1;i <= n;++i)
M *= m[i];
for(int i = 1;i <= n;++i) {
Mi = M/m[i];
ex_gcd(Mi,m[i],x,y);
res += (a[i]*Mi%M*x%M+M)%M;
}
return (res%M+M)%M;
}
10.2 扩展中国剩余定理
\(\text{现在出题人不想让}m_1,m_2,\cdots,m_n\text{两两互质了}\)
\(\text{我们的思路是先把两个方程合在一起，解此方程组，同时判断是否有解}\)
\(\text{最后得出整个方程组的解}\)
ull ex_gcd(ull a,ull b,ull &x,ull &y) {
if(!b) {
x = 1, y = 0;
return a;
}
ull res = ex_gcd(b,a%b,x,y);
ull tmp = x;
x = y;
y = tmp-a/b*y;
return res;
}
void per_CRT(ull &a1,ull &a2,ull &m1,ull &m2,bool &flag) {
ull delta = a2-a1, x, y;
ull mgcd = ex_gcd(m1,m2,x,y);
if(!(delta%mgcd)) {
x = ((x*delta/mgcd)%(m2/mgcd)+(m2/mgcd))%(m2/mgcd);
a1 = x*m1+a1;
m1 = m1*m2/mgcd;
} else flag = true;
}
ull ex_CRT(ull n,ull *a,ull *m) {
for(int i = 2;i <= n;++i) {
bool flag = false;
per_CRT(a[1],a[i],m[1],m[i],flag);
if(flag) return -1;
}
return a[1];
}
11.卢卡斯定理
11.1 卢卡斯定理
11.1.1 Lucas 定理
\(\text{设}:\)
\[n = n_k\times p^k+n_{k-1}\times p^{k-1}+\cdots+n_0 \]\[m = m_k\times p^k+m_{k-1}\times p^{k-1}+\cdots+m_0 \]\(\text{分别为}n,m\text{的}p\text{进制表达式}\)
\(\text{则有}:\)
\[C_{n}^{m} = \prod\limits_{i=0}^{k}C_{n_i}^{m_i}\pmod p \]\(\text{那么我们一路递归求下去就好了}\)
ull Lucas(ull n,ull m,ull p) {
if(!m) return 1;
return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
11.1.2 证明
11.2 扩展卢卡斯定理
11.2.1 Ex-Lucas 定理
const int size = 1024;
#define ull long long
ull quick_pow(ull a,ull n,ull p) {
ull res = 1;
a %= p;
while(n) {
if(n&1) res = res*a%p;
a = a*a%p;
n >>= 1;
}
return res;
}
void ex_gcd(ull a,ull b,ull &x,ull &y) {
if(!b) {
x = 1, y = 0;
return;
}
ex_gcd(b,a%b,x,y);
ull tmp = x;
x = y;
y = tmp-a/b*y;
}
ull inv(ull n,ull p) {
ull x, y;
ex_gcd(n,p,x,y);
return (x%p+p)%p;
}
inline ull roll(ull n,ull x,ull p) {
if(n == 0) return 1;
ull ret = 1, rem = 1;
for(ull i = 1;i <= p;++i)
if(i%x) ret = ret*i%p;
ret = quick_pow(ret,n/p,p);
for(ull i = p*(n/p);i <= n;++i)
if(i%x) rem = rem*(i%p)%p;
return roll(n/x,x,p)*ret%p*rem%p;
}
inline ull get(ull n,ull x) {
if(n < x) return 0;
return get(n/x,x)+(n/x);
}
ull multiLucas(ull m,ull n,ull x,ull p) {
ull ror = roll(n,x,p);
ull tmp1 = inv(roll(m,x,p),p), tmp2 = inv(roll(n-m,x,p),p);
ull mi = quick_pow(x,get(n,x)-get(m,x)-get(n-m,x),p);
return ror*tmp1%p*tmp2%p*mi%p;
}
ull exLucas(ull m,ull n,ull p) {
ull moyn = p;
ull bit[size] = {0}, a[size];
for(ull i = 2, temp;i*i <= p;++i)
if(p%i == 0) {
temp = 1;
while(moyn%i == 0) {
temp *= i;
moyn /= i;
}
bit[++bit[0]] = temp;
a[bit[0]] = multiLucas(m,n,i,temp);
}
if(moyn != 1) {
bit[++bit[0]] = moyn;
a[bit[0]] = multiLucas(m,n,moyn,moyn);
}
ull ans = 0;
for(ull i = 1;i <= bit[0];++i) {
ull h = p/bit[i];
ull k = inv(h,bit[i]);
ans = (ans+a[i]*h%p*k%p)%p;
}
return ans;
}
12.阶与原根
12.1 阶
12.1.1 定义
满足\(a^n\equiv 1\pmod m\)的最小正整数\(n\)称作\(a\)模\(m\)的阶，记为\(\delta_m(a)\)。
12.1.2 性质
-
\(a,a^2,\cdots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余。
-
若 \(a^n\equiv 1\pmod m\)，则 \(\delta_m(a)\mid n\)
-
若 \(a^p\equiv a^q\pmod m\)，则 \(p\equiv q\pmod {\delta_m(a)}\)
-
若 \(\gcd(a,m)=\gcd(b,m)=1\)，则 \(\delta_m(a\cdot b)=\delta_m(a)\cdot\delta_m(b)\iff\gcd(\delta_m(a),\delta_m(b))=1\)
-
若 \(\gcd(a,m) = 1\)，则 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}\)
12.2 原根
12.2.1 定义
若 \(\gcd(a,m)=1\) 且 \(\delta_m(a)=\varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根。
12.2.2 性质
1.若 \(m\ge 3,\gcd(a,m)=1\)，则 \(a\text{是模}m\text{的原根}\iff \forall p\text{是素数}\mid \varphi(m),a^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m\)（判定定理）
2.若 \(m\) 有原根，则 \(m\) 有 \(\varphi(\varphi(m))\) 个原根。（个数）
3.\(m\text{存在原根}\iff m=2,4,p^k,2\cdot p^k\ (k\in\mathbb{N}_+,p\text{为素数})\)（存在定理）
4.若 \(m\) 有原根，则最小原根不多于 \(m^{0.25}\)（这个好离谱，不过我们可以暴力找原根了）
标签：gcd,数论,text,mid,笔记,times,初步,ull,cr From： https://www.cnblogs.com/noaL02d/p/18604348/number_theory