算法基础之数学知识模板

文章目录

• • 一、质数
  • • 1.试除法判断质数
    • 2.试除法分解质因数
    • 3.筛法
  • 二.约数
  • • 1.试除法求约数
    • 2.约数个数
    • 3.约数之和
    • 4.最大公约数
  • 三、欧拉函数
  • 四、快速幂
  • 五、拓展欧几里得算法
  • 六、中国剩余定理
  • 七、高斯消元法
  • 八、组合数
  • • 1.递推
    • 2.预处理
    • 3.卢卡斯定理
    • 4.高精度组合数
    • 5.卡特兰数
  • 九、容斥原理
  • 十、博弈论
  • • 1.nim游戏
    • 2.SG函数
  • 十一、有趣的数学

一、质数

1.试除法判断质数

bool is_prime(int x)//最基础的方法
{int sqrt_x = sqrt(x);if(x < 2)return false;else{for(int i = 2; i <= sqrt_x; ++i)//或i <= n / iif(!(x % i))return false;return true;}
}

2.试除法分解质因数

void prime_resolve(int x)
{for (int i = 2; i <= x / i; ++ i){if(!(x % i)){//满足这个条件的i必为质数,因为如果i不是质数，比如i=4int cnt = 0;//那么当i=2时包含4，即包含2的部分已经被处理过了，所以能进入该判断的i必为质数while(!(x % i)){x /= i;++ cnt;}printf("%d %d\n", i, cnt);}}if(x > 1)printf("%d 1\n", x);//x中最多只含有一个大于sqrt(x)的质因子（反证法可知）puts("");
}

3.筛法

朴素筛法，O(nInn)

void get_prime(int n)
{for (int i = 2; i <= n; ++ i){if(!st[i])//标记为false则必为质数prime[cnt ++] = i;//cnt记录质数个数，prime记录有哪些质数for(int j = i + i; j <= n; j += i)//把i的倍数筛掉st[j] = true;}
}

埃式筛法，O(nloglogn)

void get_prime(int n)
{for (int i = 2; i <= n; ++ i){if(!st[i]){//与朴素筛法区别是只筛掉了质数的倍数，而后者把几乎所有数的倍数都筛了，且一个数n的质数个数不大于n/Innprime[cnt ++] = i;for(int j = i + i; j <= n; j += i)st[j] = true;}}
}

线性筛法，O(n)

void get_prime(int n)//线性筛，O(n)，关键是保证每个合数都只被它的最小的质因数筛掉，这样就保证只筛一次，n个数即筛n次，所以是线性时间
{for (int i = 2; i <= n; ++ i){//因为是把所有素数都筛出来所以是2~nif(!st[i])prime[cnt ++] = i;for(int j = 0; prime[j] <= n / i; ++j){//当i很大时，n/i几乎小于1，即之后都不需要判断了，如果i是素数，则标记，如果i不是素数，那么之前小于等于sqrt(n)的某个素数一定会把i给筛掉（因为i很大了），所以直接跳过这步判断是没有问题的st[prime[j] * i] = true;//将prime[j]*i标记为合数，  (1)   i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子,因为prime[j]是从最小的素数开始的，所以prime[j]*i一定是被其最小的素数筛掉if(!(i % prime[j]))//一个数只筛一次的关键步骤，防止多筛，如12，当i=4时，如果没有i%prime[0]即i%2协助跳出循环，那么之后会发生i*prime[1]即4*3把12筛掉的情况，很明显12的最小质因数是2，这样会导致多筛；当i=6时，才能把6*prime[0]即12筛掉，break;//; (2)  i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子}}
}

二.约数

1.试除法求约数

vector<int> get_divisor(int x)
{vector<int> res;for(int i = 1; i <= x / i; ++ i){if(!(x % i)){res.push_back(i);if(x / i != i)//防止加入两个相同的数如7*7=49res.push_back(x / i);}}sort(res.begin(), res.end());return res;
}

2.约数个数

根据算术基本定理，任意合数 x = a 1 p 1 ∗ a 2 p 2 ∗ ⋅ ⋅ ⋅ ∗ a n p n x=a1^{p1}*a2^{p2}*···*an^{pn} x=a1p1∗a2p2∗⋅⋅⋅∗anpn(a1

有约数个数 $N=(p1+1)\ast (p2+1)\ast \cdot \cdot \cdot \ast (pn+1)$

#include 
#include 
using namespace std;
typedef long long ll;
const int p = 1e9 + 7;
int main()
{int n;int x;unordered_map<int, int> primes;//用map(hash表)来存质数以及对应的个数cin >> n;ll res = 1;while(n --){cin >> x;for(int i = 2; i <= x / i; ++ i){while(!(x % i)){x /= i;primes[i] ++;//记录素数以及对应个数}}if(x > 1)//质因数分解最后还要记得特判一下是否还剩一个比较大的质数primes[x] ++;}for(auto prime : primes)//范围遍历hash表中有值的键值对res = res * (prime.second + 1) % p;cout << res << endl;return 0;
}

模板题

3.约数之和

根据算术基本定理，任意合数 x = a 1 p 1 ∗ a 2 p 2 ∗ ⋅ ⋅ ⋅ ∗ a n p n x=a1^{p1}*a2^{p2}*···*an^{pn} x=a1p1∗a2p2∗⋅⋅⋅∗anpn(a1 有约数之和 A = ( a 1 0 + a 1 1 + ⋅ ⋅ ⋅ + a 1 p 1 ) ∗ ( a n 0 + a n 1 + ⋅ ⋅ ⋅ + a n p 2 ) A=(a1^{0}+a1^{1}+···+a1^{p1})*(an^{0}+an^{1}+···+an^{p2}) A=(a10+a11+⋅⋅⋅+a1p1)∗(an0+an1+⋅⋅⋅+anp2)
求 a 0 + a 1 + a 2 + ⋅ ⋅ ⋅ + a n a^0+a^1+a^2+···+a^n a0+a1+a2+⋅⋅⋅+an的关键步骤：

while (p -- ) t = (t * a + 1) % mod;

由t=t∗a+1：
$t=1$
$t=a+1$
t = a 2 + a + 1 t=a^2+a+1 t=a2+a+1
……
t = a p + a p − 1 + … + 1 t=a^p+a^{p−1}+…+1 t=ap+ap−1+…+1

#include 
#include 
using namespace std;
const int N = 1e9 + 7;
typedef long long ll;
int main()
{int n;int x;unordered_map<int, int> primes;cin >> n;while(n --){cin >> x;for (int i = 2; i <= x / i; ++ i){while(!(x % i)){x /= i;primes[i] ++;}}if(x > 1)primes[x] ++;}ll res = 1;int a, p;for(auto prime : primes){ll t = 1;a = prime.first;//a^pp = prime.second;while(p --){t = (a * t + 1) % N;//这样求p次后就可得到a^0+a^1+···+a^n}res = (t * res) % N;}cout << res << endl;return 0;
}

模板题

4.最大公约数

辗转相除法

int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}

三、欧拉函数

由定义求欧拉函数

#include 
using namespace std;
int main()
{int n;int a;cin >> n;while(n --){cin >> a;int res = a;for(int i = 2; i <= a / i; ++ i){if(!(a % i)){while(!(a % i))a /= i;res = res / i * (i - 1);//由公式得，由于1-1/ai是小数，相乘时会发生值错误，所以要转换成(ai-1)}}if(a > 1)res = res / a * (a - 1);cout << res << endl;}return 0;
}

线性筛求欧拉函数

#include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
bool st[N];
int phi[N];
int primes[N];
int cnt;
void geteuler(int n)//在线性筛的同时求得欧拉函数
{phi[1] = 1;//1的欧拉函数是1for(int i = 2; i <= n; ++i){if(!st[i]){//质数n的欧拉函数值为n-1primes[cnt ++] = i;phi[i] = i - 1;}for(int j = 0; primes[j] <= n / i; ++ i){st[primes[j] * i] = true;if(!(i % primes[j])){//如果i%primes[j]=0，则primes[j]是i的一个公因子，那么在phi[i]=i*(1-1/a1)*(1-1/a2)*···*(1-1/an)phi[i * primes[j]] = phi[i] * primes[j];//中，primes[j]必可以化成phi[i]中的某个因子ai,而与ai的次数无关，如8%2，则phi[8]=phi[2^3]=4中有因子2，所以求phi[8*2]只需2*phi[8]=8即可，即i*primes[j]（primes[j]已经被计算过了）break;}//如果i%primes[j]不等于0phi[i * primes[j]] = phi[i] * (primes[j] - 1);//则说明primes[j]是i*primes[j]的最小质因子（因为primes[j]是从小到大开始枚举的质数）}//phi[i]* primes[j] * (primes[j] - 1) / (primes[j] = phi[i]*(primes[j]-1)}
}

模板题
欧拉定理

证明：数学知识（2）44：00或知乎链接
n为质数时则有费马小定理；

四、快速幂

二进制的思想理解快速幂

ll fm(int a, int k, int p)//求a^k%p
{ll res = 1;//任意数都可用二进制表示，所以k可以用01串表示while(k){//即a^k可用a^0*a^1*a^i*a^n表示，如2^5=2^(101)=2^4*2^1= 1*2^(100) * 0*2^(010) * 1*2*(001)if(k & 1)//如果二进制串的最后一位为1，表示需要乘以一个a,为0则不用管res =res * a % p;k >>= 1;//把二进制串当前位去掉a = (ll)a * a % p;//由于指数位数少了1，则表示底数应该平方，如3^4=3^(100)， 指数100右移一位后， a^(10)=a^2 ,则a=3^2,即进行了平方}return res;
}

应用：求乘法逆元（逆元将除法转换成乘法）

模板题

五、拓展欧几里得算法

裴蜀定理：
若a,b 是整数,且$gcd(a,b)=d$，那么对于任意的整数 $x,y$, $ax+by$ 都一定是 d的倍数，特别地，一定存在整数$x,y$，使$ax+by=d$成立
推论：对于方程$ax+by=1$，只有当整数$a,b$互质时，方程才有整数解。
应用：对于方程$ax+by=z$，只有满足$gcd(a,b)\mid z$，方程才有整数解。
(设$gcd(a,b)=d(a1x+b1y=d))$,则两边同时扩大m倍，得$ax+by=z(即z=d\ast m)$，所以要有$gcd(a,b)|z$)

题解
正常版：

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

递归复杂版

void exgcd(int a, int b, int &x, int &y)
{if(!b){x = 1;y = 0;}else{//结合上个版本这里的递归看！exgcd(b, a % b, y, x);//由于引用，且x,y顺序对调，这里的y接收回溯的x，x接收回溯的y，即在这里y=x2，x=y2y -= a / b * x;//原本x1=y2,而这里由于x2=y2，所以x=x}
}
exgcd(a, b, x, y);

经过拓展欧几里得算法后可以得到方程的一组特解$(x0,y0),d=gcd(a,b)$,即$a\ast x0+b\ast y0=d$;
通解$x=x0-b/d\ast k$
$y=y0-b/d\ast k$ (因为$d$是$b$约数，所以$b/d$
必为整数)

模板题

用拓展欧几里得算法解同余方程
对于$a\ast x0+m\ast y0=gcd(a,m)$,左右两边同时乘以一个k后有$a\ast x+m\ast y=b$，则$b/gcd(a,m)$即为k，所以$x=x0\ast k$

#include //解同余方程
using namespace std;
typedef long long ll;
int exgcd(int a, int b, int &x, int &y)
{if(!b){x = 1;y = 0;return a;//a即为最终的d，最大公约数}else{int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;}
}
int main()
{int n;int a, b, m;int x, y;cin >> n;while(n --){scanf("%d%d%d", &a, &b, &m);int d = exgcd(a, -m, x, y);if(b % d)//由裴蜀定理，无解puts("impossible");else {x = (ll)x * b / d % m;//%m防止溢出cout << x << endl;}}return 0;
}

六、中国剩余定理

先跳过，之后补上。。。

七、高斯消元法

模板题
题解

八、组合数

1.递推

a,b小于2000时使用；
排列数可以看成是一个下三角，如

1
1 1
1 2 1
1 3 3 1
······

首先讲第一列的值都初始化成1，然后有递推公式：

$f[i][j]=f[i-1][j]+f[i-1][j-1]$

理解：
时间复杂度：O( N 2 N^2 N2)

const int N = 2010, mod = 1e9 + 10;
typedef long long ll;
ll f[N][N];
void comb(void)
{for(int i = 0; i <= 2000; ++ i){for(int j = 0; j <= i; ++ j){if(!j)  //初始化，第一列恒置为1f[i][j] = 1;else    //递推公式f[i][j] = (f[i - 1][j] +f[i - 1][j - 1]) % mod;}}
}

2.预处理

a,b小于 1 0 5 10^5 105时使用；

由 C a b = a ! b ! ( a − b ) ! C_{a}^{b}=\frac{a!}{b!\left( a-b \right) !} Cab​=b!(a−b)!a!​
该公式求得组合数，而除法转换成求逆元；
时间复杂度：O($nlogn$)

#include 
using namespace std;
const int N = 1e5 +10, mod = 1e9 +7;
typedef long long ll;
ll fact[N];     //阶乘
ll infact[N];   //逆元的阶乘
ll qmi(int a, int k, int p)//快速幂求逆元
{ll res = 1;while(k){if(k & 1)res = res * a % p;a = (ll)a * a % p;k >>= 1;}return res;
}
int main()
{fact[0] = infact[0] = 1;for(int i = 1; i < N; ++ i){    //递推求阶乘fact[i] = fact[i - 1] * i % mod;//x=b^(p-2)%p,这里相当于是x=i^(mod-2)%mod，所以乘x就相当于除i,因为infact表示阶乘逆元和,infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;//因为infact表示除以i的阶乘的逆元,所以乘infact[i-1]，相当于乘上1/(i-1)!.}//又因为乘x相当于除以i,所以infact[i-1]乘上x等于1/i!,也就等于infact[i];int n;ll ans = 1;cin >> n;int a, b;while(n --){scanf("%d%d", &a, &b);printf("%lld\n", fact[a] * infact[a-b] % mod * infact[b] % mod);    //除法转换成逆元，模两次防溢出}return 0;
}

模板题

3.卢卡斯定理

a,b小于 1 0 18 10^{18} 1018时使用；
C a b ≡ C a % p b % p ∗ C a p b p ( m o d p ) C_{a}^{b}\equiv C_{a\%p}^{b\%p}*C_{\frac{a}{p}}^{\frac{b}{p}}\left( mod\,\,p \right) Cab​≡Ca%pb%p​∗Cpa​pb​​(modp)
组合数直接运算：
C a b = a ∗ ( a − 1 ) ∗ ⋅ ⋅ ⋅ ∗ ( a − b + 1 ) 1 ∗ 2 ∗ ⋅ ⋅ ⋅ ∗ b C_{a}^{b}=\frac{a*\left( a-1 \right) *···*\left( a-b+1 \right)}{1*2*···*b} Cab​=1∗2∗⋅⋅⋅∗ba∗(a−1)∗⋅⋅⋅∗(a−b+1)​
除法转换成对p的逆元；

#include 
using namespace std;
typedef long long ll;
int p;
int qmi(int a, int k)
{int res = 1;while(k){if(k & 1)res = (ll)res * a % p;a = (ll)a * a % p;k >>= 1;}return res;
}
int C(int a, int b)//额外写一个求组合数，按照最原始定义来求
{int res = 1;for(int i = 1, j = a; i <= b; ++ i, -- j){res = (ll)res * j % p * qmi(i, p - 2) % p ;//除i转换为求i的在p下的乘法逆元}return res;
}
ll lucas(ll a, ll b)
{if(a < p && b < p)//如果a,b都比p小就没必要用卢卡斯定理了，否则就用卢卡斯定理，下式同理return C(a, b);elsereturn C(a % p, b % p) * lucas(a / p, b / p) % p;//卢卡斯定理
}
int main()
{int n;ll a, b;cin >> n;while(n --){cin >> a >> b >> p;cout << lucas(a, b) << endl;}return 0;
}

模板题

4.高精度组合数

当题目中不允许取模而组合数太大且数量不多时使用；
质因数分解+高精度
参考题解

#include 
#include 
using namespace std;
const int N = 5010;
int primes[N];
int sum[N];
int st[N], cnt;
void get_primes(int n)//线性筛
{for(int i = 2; i <= n; ++ i){if(!st[i])primes[cnt ++] = i;for(int j = 0; primes[j] <= n / i; ++ j){st[primes[j] * i] = true;if(i % primes[j] == 0)break;}}
}
int get_n(int n, int p)//求出n!中p的数目
{int res = 0;while(n){res += n / p;n /= p;}return res;
}
vector<int> mul(vector<int> a, int b)//高精度乘法
{vector<int> c;int t = 0;for(int i = 0; i < a.size(); ++ i){t += a[i] * b;c.push_back(t % 10);t /= 10;}while(t) {c.push_back(t % 10);t /= 10;}return c;
}
int main()
{int a, b;cin >> a >> b;get_primes(a);for(int i = 0; i < cnt; ++ i){int prime = primes[i];  //取当前的质数sum[i] = get_n(a, prime) - get_n(b, prime) - get_n(a - b, prime);//求得该质数因子在该组合数中的数目，即分母的因子数减去分子的因子数}vector<int> ans;ans.push_back(1);for(int i = 0; i < cnt; ++ i){//遍历每个a的质数因子for(int j = 0; j < sum[i]; ++ j){//当前a的质数因子的个数ans = mul(ans, primes[i]);//都乘上当前该质数因子}}for(int i = ans.size() - 1; i >= 0; -- i)printf("%d", ans[i]);cout << endl;return 0;
}

模板题

5.卡特兰数

a n s = C 2 n n − C 2 n n − 1 = C 2 n n n + 1 ans=C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n+1} ans=C2nn​−C2nn−1​=n+1C2nn​​
卡特兰数推导+题解
用逆元求组合数；

#include 
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, N = 2e5 + 10;
int fact[N], infact[N];
int qmi(int a, int k)
{int p = mod;int res = 1;while(k){if(k & 1)res = (ll)res * a % p;a = (ll)a * a % p;k >>= 1;}return res;
}
void init()
{fact[0] = infact[0] = 1;for(int i = 1; i < N; i ++){fact[i] = (ll)fact[i - 1] * i % mod;infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2) % mod;}return;
}
int main()
{init();int n;cin >> n;int res = (ll)fact[2 * n] * infact[n] % mod * infact[n] % mod * qmi(n + 1, mod - 2) % mod;//除法都转换成求乘法逆元cout << res << endl;return 0;
}

模板题

九、容斥原理

⋃ i = 1 m S i = ( S 1 + S 2 + … + S i ) − ( S 1 ∩ S 2 + S 1 ∩ S 3 + … + S m − 1 ∩ S m ) + ( S 1 ∩ S 2 ∩ S 3 + … + S m − 2 ∩ S m − 1 ∩ S m ) + … + ( − 1 ) m − 1 ( ⋂ i = 1 m S ) \bigcup_{i=1}^m{S_i}=(S_1+S_2+…+S_i)-\left( S1\cap S2+S1\cap S3+…+S_{m−1}\cap S_m \right) +\left( S_1\cap S2\cap S3+…+S_{m−2}\cap S_{m−1}\cap S_m \right) +…+\left( -1 \right) ^{m-1}\left( \bigcap_{i=1}^m{S} \right) i=1⋃m​Si​=(S1​+S2​+…+Si​)−(S1∩S2+S1∩S3+…+Sm−1​∩Sm​)+(S1​∩S2∩S3+…+Sm−2​∩Sm−1​∩Sm​)+…+(−1)m−1(i=1⋂m​S)
集合为奇则加，否则减；
精彩题解

#include 
using namespace std;
typedef long long ll;
int main()
{int n, m;int p[20];cin >> n >> m;for(int i = 0; i < m; ++ i)cin >> p[i];int res = 0;//答案个数for(int i = 1; i <= 1 << m - 1;++ i){//从1到11···11(m位1)int t = 1; //质数乘积int s = 0;  //判断当前集合性质奇偶性，来分析是要加还是减去tfor(int j = 0; j < m; ++ j){if((i >> j) & 1){//如果当前位为1，代表选中该位，即乘上当前该位对应的质数if((ll)t * p[j] > n){//如果当前乘积太大了t = -1;break;}s ++;//选中集合中内的元素个数t *= p[j];}}if(t == -1)//意味着乘积t太大了，超过了n，不考虑当前情况continue;if(s & 1)//奇数则加，偶数则减res += n / t;elseres -= n / t;}cout << res << endl;return 0;
}

模板题

十、博弈论

1.nim游戏

nim游戏

先手必败状态： a 1 ⊕ a 2 ⊕ a 3 ⊕ ⋅ ⋅ ⋅ ⊕ a n = 0 a_1\oplus a_2\oplus a_3\oplus ···\oplus a_n=0 a1​⊕a2​⊕a3​⊕⋅⋅⋅⊕an​=0
先手必胜状态：
a 1 ⊕ a 2 ⊕ a 3 ⊕ ⋅ ⋅ ⋅ ⊕ a n ≠ 0 a_1\oplus a_2\oplus a_3\oplus ···\oplus a_n\ne 0 a1​⊕a2​⊕a3​⊕⋅⋅⋅⊕an​​=0

模板题

2.SG函数

大佬精彩博客
重点是用代码模拟SG函数的第一部分，即遍历所有可选数字集合，并向下递归，最后mex操作找到未出现过的最小的自然数作为答案；

模板题

#include 
#include 
#include 
using namespace std;
const int N = 110, M = 1e4 + 10;
int s[N];
int f[M];
int k;
int sg(int x)
{if(f[x] != -1)//如果非-1，说明已经存储过了，直接用就行（同一组合的s[i]，x对应的f[x]值唯一）return f[x];unordered_set<int> S;//hash表存有向图for(int i = 0; i < k; ++ i){//遍历所有可选的数字集合int sum = s[i];if(x >= sum)//减去sum后非负的话则继续向下递归S.insert(sg(x - sum));}for(int i = 0; ; ++ i){//mex运算操作，选取一个最小的未出现过的自然数作为最终答案if(!S.count(i))return f[x] = i;}
}
int main()
{int  n;memset(f, -1, sizeof(f));//全部初始化成-1，便于后续处理cin >> k;for(int i = 0; i < k; ++ i)cin >> s[i];cin >> n;int res = 0;int x;for(int i = 0; i < n; ++ i) {cin >> x;res ^= sg(x);//和简单nim游戏一样的操作}if(res)puts("Yes");elseputs("No");return 0;
}

十一、有趣的数学

n条互不平行的直线的交点数为$n\ast (n-1)/2$

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！