快速幂
定义
快速幂，是一个在 \(\Theta(\log n)\) 的时间内计算 \(a^n\) 的小技巧，而暴力的计算需要 \(\Theta(n)\) 的时间。
解释
定义快速幂函数为 \(q(x,n)\)，则
实现
#include <iostream>
using namespace std;
long long a, b, p;
long long q(long long x, long long n)
{
if(n == 0) return 1;
long long r = 0;
if(n == 1) return a;
r = q(x, n / 2) % p;
r = r * r % p;
if(n % 2) r = r * x % p;
return r;
}
int main()
{
cin >> a >> b >> p;
cout << a << "^" << b << " mod " << p << "=" << q(a, b) % p;
return 0;
}
唯一分解定理
\(\forall n\in \mathbf{N}_+\) 均可以被分解为有限个质数的乘积。
调和级数
定义
\(\sum\limits_{i=1}^{n}\dfrac{1}{i}\) 被称为调和级数，它是发散的，即没有极限。
调和级数的部分和
\(\sum\limits_{i=1}^{n}\dfrac{1}{i}=\ln n + \gamma+\epsilon_k\)。其中 \(\gamma\) 是欧拉-马歇罗尼常数，而 \(\epsilon_k\approx\dfrac{1}{2k}\) ，并且随着 \(k\) 趋于正无穷而趋于 \(0\)。这个结果由欧拉给出。
gcd 与 lcm
\(\forall A,B\in\mathbf{N}_+\)，根据唯一分解定理，有 \(A=\prod\limits_{i=1}^{n}p_i^{a_{i}},B=\prod\limits_{i=1}^{n}p_i^{b_{i}}\)，其中 \(p_i\) 为质数。
则有 \(\gcd(A,B)=\prod\limits_{i=1}^{n}p_i^{\min(a_i,b_i)}\)，\(\text{lcm}(A,B)=\prod\limits_{i=1}^{n}p_i^{\max(a_i,b_i)}\)。
还有 \(\min(a,b) +\max(a,b) = a+b\)。
所以
自然对数的底
引入
银行推出了活动，定期存款存一年的 \(\frac{1}{n}\) 时，利率为 \(\frac{1}{n}\)，求本金为 \(100\text{元}\) 时反复存取直至一年时最多能拿多少钱。
例：存半年能拿 \(100\times (1 + 50\%)^2 = 225\text{(元)}\)。
化简一下，题意就变为了：求
我们定义：
其中 \(e\) 是一个无理数，其值约等于 \(2.718281828459\cdots\)。
以 \(e\) 为底的对数被称为自然对数，简记为 \(\ln x\)。即 \(\log_ex=\ln x\)。
（\(\ln\) 读作 natural log，也可读作 /lɔn/）
exgcd
辗转相除法
定义
扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求
的一组可行解。
推导过程
因为：
就有：
即为：
当 \(b=0\) 时，有 \(x=1,y=0\)。
当 \(b\neq 0\) 时，递归求解。
Code
void exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0; //递归边界
return;
}
else {
exgcd(b, a % b, x, y);
int tmp = x;
x = y, y = tmp - a / b * y; // 继续递归
}
}
模运算意义下的逆元
定义
对于任意的 \(\gcd(a,p)=1\)，存在唯一的 \(x(0\leq x\leq p-1)\)，使得 \(ax\bmod p = 1\)。称 \(x\) 为 \(a\) 在 \(\bmod\ p\) 意义下的乘法逆元。
求法
exgcd
证明：
令 \(y=\lfloor \dfrac{ax}{p} \rfloor\)，则：
用 exgcd 求解即可。
欧拉定理
欧拉（Euler）定理：
其中 \(\varphi\) 为欧拉函数，\(\varphi (n)\) 表示不大于 \(n\) 的整数中与 \(n\) 互质的数的个数，定义 \(\varphi(1) =1\)。
故 \(a\) 在 \(\bmod\ p\) 意义下的乘法逆元为 \(a^{\varphi(p)-1}\)。
费马小定理
费马小定理：当 \(p\) 为质数时，有 \(a^{p-1}\bmod p = 1\)。
故 \(a\) 在 \(\bmod\ p\) 意义下的乘法逆元为 \(a^{p-2}\)。
当 \(p\) 为质数时，\(\varphi(p)=p-1\)，故费马小定理求逆元是欧拉定理求逆元的一种特殊情况。
欧拉筛
筛质数
在欧拉筛中，每一个合数都是被最小的质因子筛掉。
void init(int n) {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
pri[cnt++] = i;
}
for (int j = 0; j < cnt && 1ll * i * pri[j] <= n; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) { // 换言之，i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
// pri[j]的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break 就好了
break;
}
}
}
}
因为 prime[] 中的质数是递增的，当 \(i\mid prime_j\)，那么 \(i\times prime_{j+1}\) 一定会被 \(prime_j\) 乘 某个数 筛掉，接下来的数同理，因此在满足 i % prime[j] == 0 时即可 break 。
筛积性函数
积性函数的定义：
若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y\in\mathbf{N}_+,\gcd(x,y)=1\) 都有 \(f(x\times y)=f(x)\times f(y)\)，则 \(f(n)\) 为积性函数。
将 \(x\) 分类讨论：
- \(x\) 为质数，则 \(f(x)\) 直接计算。
- \(i\bmod prime_j \neq 0\)，则根据积性函数定义，有 \(f(i\times prime_j)=f(i)\times f(prime_j)\)
- \(i\bmod prime_j = 0\)，则 \(i\) 的最小质因子也为 \(prime_j\)，记 \(prime_j\) 在 \(i\) 的质因数中出现次数为 \(t\)，显然 \(\dfrac{i}{prime_j^t}\) 与 \(prime_j^{t+1}\) 互质。所以 \(f(i\times prime_j)=f(\dfrac{i}{prime_j^t})\times f(prime_j^{t+1})\)
筛欧拉函数
易证 \(\varphi\) 为积性函数。
对于任意的质数 \(p\)，有 \(\varphi(p)=p-1\)，\(\varphi(p^a)=p^{a-1}(p-1)\)。
证明：
当 \(p\) 为质数时，在不大于 \(p\) 的正整数中，每 \(p\) 个数就有 \(p-1\) 个数与 \(p\) 互质。
所以 \(\varphi(p^a)=p^a\times\frac{p-1}{p} = p^{a-1}(p-1)\)。\(\Box\)
故
将 \(x\) 分类讨论：
- \(x\) 为质数，则 \(\varphi(x)=x-1\)。
- \(i\bmod prime_j \neq 0\)，则根据积性函数定义，有 \(\varphi(i\times prime_j)=\varphi(i)\times \varphi(prime_j) = \varphi(i)\times (prime_j-1)\)
- \(i\bmod prime_j = 0\)，则 \(i\) 包含了 \(prime_j\) 的所有质因子，
Code：
//vis[i] 存储 i 是否为合数
void init() {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) {
break;
}
}
}
}
博弈论
寄，没听懂