note 信竞中的数学

标签：frac gcd 质数 times note 数学 竞中 equiv mod

1.质数和约数

质数：

若一个正整数无法被除了 \(1\) 和它本身之外的任何自然数整除，则称该数为质数。

质数的判定：

1. 试除法

2. Miller-Robbin

Eratosthenes筛法

每个合数 \(a\) 一定可以写成 \(p\times x\) 的形式，其中 \(p\) 是素数，\(x\) 是倍数 \((x\neq 1)\)。

对于每个 \(1\) 到 \(n\) 内的素数 \(p\)，枚举倍数 \(x\) 把 \(p\times x\) 标记为合数，这就是埃氏筛法。

筛选时做一个改进：对于素数 \(p\)，只筛倍数 \(x\ge p\) 的数，因为如果 \(x<p\) ,则 \(x\) 中一定有比 \(p\) 小的素因子，\(p\times x\) 会在前面筛选过程中被筛出。

因此只需考虑 \(2\) 到 \(n\) 范围的素数。

时间复杂度：\(O(nloglogn)\)

p[0]=p[1]=true;
for(int i=2;i<=n;i++){
	if(p[i])
        continue;
	for(int j=i;i*j<=n;++j)
        p[i*j]=true;
}

线性筛法

在 Eratosthenes 筛法中，合数会被重复标记。

如果每个合数只被它的最小质因数标记，那么每个数最多只会被标记一次。

依次考虑 \(2\) 到 \(n\) 之间的每一个数 \(i\)。

如果 \(i\) 是质数，则将其保存到质数表中。

否则利用 \(i\) 和质数表中的 \(pri[j]\) 筛去 \(i\times pri[j]\)。

筛的过程中要确保 \(pri[j]\) 是 \(i\times pri[j]\) 的最小质因子。

p[0]=p[1]=true;
for(int i=2;i<=n;i++){
	if(!p[i]) 
    	pri[++cnt]=i;
	for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
	    p[i*pri[j]]=true; 
        if(!i%pri[j])
            break;
	} 
}

算术基本定理

若整数 \(n \ge 2\)，那么 \(n\) 一定可以唯一地表示为若干质数的乘积。形如

\[n = P_1^{c_1}P_2^{c_2} … P_k^{c_k} \]

(\(P_i\) 为质数，\(c_i\ge 0\))

约数

若整数 \(n\) 除以整数 \(d\) 的余数为 \(0\)，即 \(d\) 能整除 \(n\)。

则称 \(d\) 是 \(n\) 的约数，\(n\) 是 \(d\) 的倍数。记为 \(d|n\)。

若正整数 \(n\) 被唯一分解为 \(n=P_1c_1P_2c_2⋯P_mc_m\)，其中 \(c_i\) 都是正整数，\(P_i\) 都是质数。

且满足$ P_1<P_i<...<P_m$，则 \(n\) 的正约数集合为 ：

\[P_1^{c_1}P_2^{c_2}…P_k^{c_k} |0 \le b_i \le c_i \]

\(n\) 的正约数个数为 ：

\[(c_1+1)\times (c_2+1)\times⋯(c_m+1)=\prod_{i=1}^m(c_i+1) \]

n 的所有正约数的和为：

\[(1 + p_1 + p_1^2+...+p_1^{c_1})\times...\times(1 + p_m+p_m^2 + p_m^{c_m}) = \prod_{i = 1}^m(\sum_{j = 0}^{c_1}(p_i)^j) \]

求正约数集合

求 \(n\) 的正约数集合：试除法

一个整数 \(n\) 的约数个数上界为 \(2\sqrt{n}\)。

求 \(1\) 到 \(n\) 每个数的正约数集合：倍数法

\(1\) 到 \(n\) 每个数的约数个数的总和大约为 \(nlogn\)。

反素数

对于任何正整数 \(x\)，其约数个数记作 \(g(x)\)。例如：\(g(1)=1\)，\(g(6)=4\)。

如果某个正整数满足：

对于任意的 \(0<i<x\)，都有 \(g(x)>g(i)\)，那么称 \(x\) 为反素数。

求不超过 \(N\) 的最大的反素数。

\(1\le N\le 2\times 10^9\)

\(1\) 到 \(N\) 中最大的反素数，就是 \(1\) 到 \(N\) 中约数个数最多的数中最小的一个。

\(1\) 到 \(N\) 中任何数的不同质因子都不会超过 \(10\) 个，且所有质因子的指数总和不超过 \(30\)。

\(\forall x \in [1,n]\)，\(x\) 为反素数的必要条件是：\(x\) 分解质因数后可写作

\[2^{c_1}\times 3^{c_2}\times 5^{c_3}\times 7^{c_4} \times 11^{c_5} \times 13^{c_6} \times 17^{c_7} \times 19^{c_8} \times 23^{c_9}\times 29^{c_{10}} \]

并且

\[c_1 \ge c_2 \ge...\ge c_{10}\ge 0 \]

综上，DFS 即可。

余数之和

给出正整数 \(n\) 和 \(k\)，请计算：

\[G(n,k)=\sum_{i=1}^nk\mod i \]

\[G(n,k)=\sum_{i=1}^nk\mod i=n*k-\sum^n_i=\lfloor\frac{k}{i}\rfloor \times i \]

最大公约数和最小公倍数

令 \(a\) 和 \(b\) 是不全为 \(0\) 的两个整数。

能使 \(d|a\) 和 \(d|b\) 的最大整数称为 \(a\) 和 \(b\) 的最大公约数，用 \(gcd(a,b)\) 表示。

或者记为 \((a,b)\)。

能使 \(a|d\) 和 \(b|d\) 的最小整数称为 \(a\) 和 \(b\) 的最小公倍数，用 \(lcm(a,b)\) 表示。

或者记为 \([a,b]\)。

求解最大公约数

更相减损术：

\[\forall a,b\in \mathbb{N},b\neq0 \]

有

\[gcd(a,b)=gcd(b,a−b)=gcd(a,a−b) \]

\[\forall a,b\in \mathbb{N} \]

有

\[gcd(2a,2b)=2gcd(a,b) \]

欧几里得算法（辗转相除法）：

\[\forall a,b\in \mathbb{N},b\neq0,gcd(a,b)=gcd(a,a\mod b) \]

最小公倍数

\[lcm(a,b)= \frac{ab}{gcd(a,b)} \]

若 \(a|m\) 且 \(b|m\)，则 \(lcm\ a,b|m\)

若 \(m,a, b\) 是正整数，则 \(lcm (ma,mb)=m\times lcm(a,b)\)

\[lcm(a_1, a_2) = a_1a_2/gcd(a_1,a_2) \]

\[lcm(a_1,a_2,a_3)=lcm(lcm(a_1,a_2),a_3) \]

互质与欧拉函数

\(\forall a,b\in \mathbb{n}\)，若 \(gcd(a,b)=1\)，则称 \(a,b\) 互质。

\(1\) 到 \(N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记为 \(\varphi(N)\)。

若 \(N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)，则：

\[\varphi(N)=N \times\frac{p_1 - 1}{p_1}\times\frac{p_2 - 1}{p_2}\times...\times\frac{p_m - 1}{p_m} = N \times \prod_{p|N}(1 - \frac{1}{p}) \]

1. \(\forall n>1\)，\(1\) 到 \(n\) 中与 \(n\) 互质的数的和为 \(n\times \varphi (n)/2\)。

2. 若 \(a\)，\(b\) 互质，则 \(\varphi ab=\varphi\ a\ \varphi (b)\)

积性函数：\(a\)，\(b\) 互质时，有 \(f(ab)=f(a)\times f(b)\)，那么称函数 \(f\) 为积性函数。

3. 若 \(f\) 是积性函数，且在算术基本定理中 \(n=\varsigma i=1m\ p_i\ c_i\) 则 \(f n=\varsigma i=1m\ f(p_i\ c_i)\)。

4. 设 \(p\) 为质数，若 \(p|n\) 且 \(p\ 2\ |n\) 则 \(\varphi n=\varphi(\frac{n}{p})\times p\)。

5. 设 \(p\) 为质数，若 \(p|n\) 且 \(p\ 2 \nmid n\) 则 \(\varphi n=\varphi(\frac{n}{p})\times (p-1)\)

6. \(\sum \limits_{d|n}\varphi(d)=n\)

线性筛求欧拉函数

for(int i=2;i<=n;i++){
	if(!p[i]){
      	pri[++cnt]=i;
      	phi[i]=i-1;
    }
	for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
		p[i*pri[j]]=true; 
		if(!i%pri[j]) {
            phi[i*pri[j]]=phi[i]*pri[j]; 
            break;
        }
		else
          	phi[i*pri[j]]=phi[i]*(pri[j]-1);
	} 
}

2.同余

模运算

\((a+b)\mod m=((a\mod m)+(b\mod m))\mod m\)

\((a-b)\mod m=((a\mod m)-(b\mod m))\mod m\)

\((a\times b)\mod m=((a\mod m)\times(b\mod m))\mod m\)

基本概念

除法定理：对于任何整数 \(a\) 和任何正整数 \(b\)，存在唯一整数 \(q\) 和 \(r\)，满足 \(0 \le r < m\) 且 \(a = qm+r\)，其中 \(q=\lfloor\frac{a}{m}\rfloor\) 为商，\(r=a\mod m\) 为余数。

同余：如果 \(a \mod m=b \mod m\)，即 \(a\), \(b\) 除以 \(m\) 所得的余数相等，记作：\(a\equiv b(\mod m)\)。

裴蜀定理

对任何整数 \(a\),\(b\)，关于未知数 \(x\) 和 \(y\) 的线性不定方程（称为裴蜀等式）：\(ax+b\)

方程有整数解（当且仅当 \(c\) 是 \(gcd(a,b)\) 的倍数）。

裴蜀等式有解时必然有无穷多个解。
\(ax+by=c\) 有解的充要条件为 \(gcd(a,b)|c\)。

一定存在 \(x\),\(y\) 满足 \(ax+by=gcd(a,b)\)。

\(a,b\) 互质等价于 \(ax+by=1\) 有解。

扩展欧几里德算法

void exgcd(int a,int b,int &x,int &y){
	if(!b){
        x=1,y=0; 
        return;
    }
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}

逆元求解

\(ax \equiv 1(\mod m)\)

利用扩展欧几里得算法求逆元，相当于解方程：\(ax+my=1\)。

利用欧拉定理求逆元，有 \(a\times a^{\varphi(m)−1}\equiv 1(\mod m)\) ，可用快速幂求解。

当 \(m\) 为质数时，答案为 \(qpow(a,m-2)\mod m\)。

线性求逆元：递推

求 \(1\) 到 \(n\) 所有数模 \(p\)（\(p\) 为质数且 \(n<p\)）意义下的逆元。

当求 \(i\) 的逆元时，考虑 \(p=iq+r\)，有：\(iq+r \equiv 0(\mod p)\)。

由于 \(p\) 是质数，所以 \(r\) 不为 \(0\)，\(r\) 的逆元存在。

等式两边同乘 \(i^{-1}r^{-1}\)，得到 \(qr^{-1} + i^{-1}\equiv 0(\mod p)\)。

因此：\(i^{−1}\equiv −qr^{−1} \equiv −p_i(p \mod i)^{-1} (\mod p)\)。

for(int i=2;i<=n;i++) 
  	inv[i]=inv[p%i]*(p-p/i)%p;

线性同余方程

形如 \(ax\equiv c(\mod m)\) 的方程为线性同余方程。

线性指 \(x\) 的系数为一次。

该方程可转化为 \(ax+my=c\) 后利用扩展欧几里得算法求解。

根据裴蜀定理，方程有解当且仅当 \(gcd(a,m)|c\)。

线性同余方程组

考虑形如 \(x\equiv a_i (\mod m_i)\) 的若干方程联立得到的方程组，如：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

\[|x\equiv 2(mod 3)......(1) \]

\[|x\equiv 3(mod 5)......(2) \]

\[|x\equiv 2(mod 7)......(3) \]

中国剩余定理

对于同余方程组 \(x\equiv a_i(\mod m_i) (i=1...n)\)，若 \(m_i\) 两两互质，则 \(x\) 在 \(\mod M\) 下有唯一解。

其中 \(M=m_1m_2...mn\)。

令 \(M_i=Mm_i\) 有 \((M_i,m_i)=1\)，\(M_i\) 关于模 \(m_i\) 的逆元存在，设逆元为 \(t_i\)。

\[M_i\ t_i\equiv1(\mod m_i), M_i\ t_i\equiv0(\mod m_j) (j\neq i) \]

\[a_i\ M_i\ t_i\equiv a_i(\mod m_i), a_i\ M_i\ t_i\equiv 0 (\mod m_j)(j\neq i) \]

故解为

\[x\equiv\sum_{i=1}^{n}a_i\ M_i\ t_i(\mod M)。 \]

\[a_i={2,3,2},m_i={3,5,7},M=3\times 5\times 7=105 \]

\[M_i={\frac{105}{3},\frac{105}{5},\frac{105}{7}}={35,21,15} \]

\[t_i={inverse(35, 3),inverse(21, 5),inverse(15, 7)}={2,1,1} \]

\[x\equiv2\times(35\times2)+3\times(21\times1)+2\times(15\times1) \]

\[x\equiv 233\equiv 23(\mod 105) \]

通解

\[x=23+105k(k\in z) \]

for(int i=1;i<=n;i++)
  	M*=a[i];
for(int i=1;i<=n;i++){
	m[i]=M/a[i];
	exgcd(m[i],a[i],t[i],y);
	ans+=b[i]*m[i]%M*t[i]%M;
	ans%=M;
}

3.组合计数

加法原理和乘法原理

加法原理：

完成一件事的方法有 \(n\) 类，第 \(i\) 类包括 \(a_i\) 种不同的方法，且这些方法互不重合。

则完成这件事共有 \(a_1+a_2+...+a_n\) 种不同的方法。

乘法原理：

完成一件事需要 \(n\) 个步骤，第 \(i\) 个步骤有 \(a_i\) 种不同的完成方法，且这些步骤互不干扰。

则完成这件事共有 \(a_1\times a_2\times ...\times a_n\) 种不同的方法。

排列数和组合数

从 \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列，产生的不同排列的数量为：

\[A_n^m=\frac{n!}{(n-m)!}=n\times(n−1)\times...\times (n−m+1) \]

从 \(n\) 个不同元素中取出 \(m\) 个组成一个集合（不考虑顺序），产生的不同集合数量为：

\(C_n^m = \frac{n!}{(n - m)!}=\frac{n \times(n - 1) \times...\times(n - m + 1)}{m \times(m - 1)\times......\times}2\times1\)

组合数的性质

\(C_n^m=C_n^{n−m}\)

\(C_n^m=C_{n−1}^m+C_{n-1}^{m−1}\)

\(C_n^0+C_n^1 +C_n^2+...+C_n^n= 2^n\)

二项式定理

\[(a+b)^n=\sum_{k=0}^nC_n^ka^kb^{n-k} \]

4.附录

\(|\) 整除

\(a|b\) 意思为 \(b\) 能整除 \(a\)

"\(\nmid\)"

\(a \nmid b\)意思为 \(b\) 不能整除 \(a\)

\(\equiv\) 同余

$\in\ \ni\ \notin $他的头朝哪边另一边就是这边的因数，斜杠则代表不是。

\(\forall\)任意

标签：frac,gcd,质数,times,note,数学,竞中,equiv,mod
From： https://www.cnblogs.com/xiaoluotongxue2012/p/17751782.html