寂静的角落 星空在前,路在脚下
加法逆元 Additive Inverse
发布于: 2021-03-03 更新于: 2021-04-05 分类于: 算法

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
/*
template <typename T>
inline T additive_inverse(T n);
求 n 的加法逆元
T 必须为整型类
*/
template <typename T>
inline T additive_inverse(T n) {
return -n;
}
阅读更多
费马小定理 Fermat's little theorem
发布于: 2021-03-03 更新于: 2021-04-05 分类于: 算法

内容

形式一

若 $p$ 为质数,且 $a$ 与 $p$ 互质(即 $(a, p) = 1$ ),则有

$$a^{p - 1} \equiv 1 \pmod{p}$$

形式二<...

阅读更多
线性求欧拉函数
发布于: 2021-03-03 更新于: 2021-04-05 分类于: 算法

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
template <typename T>
inline void get_phi(T n, T *phi_table);
线性求 n 以下的欧拉函数,并存到 phi_table 中
T 必须为整形类
*/
template <typename T>
inline void get_phi(T n, T *phi_table) {
for (T i = 2; i <= n; ++i) phi_table[i] = 0;
phi_table[1] = 1;
for (T i = 2; i <= n; ++i)
if (!phi_table[i])
for (T j = i; j <= n; j += i) {
if (!phi_table[j]) phi_table[j] = j;
phi_table[j] = phi_table[j] / i * (i - 1);
}
}
阅读更多
欧拉函数 Euler function
发布于: 2021-03-03 更新于: 2021-04-28 分类于: OI

第一次看的时候我直接晕。

阅读更多
埃拉托斯特尼筛法 κόσκινον Ἐρατοσθένους
发布于: 2021-02-17 更新于: 2021-04-28 分类于: OI

一个古老的算法。

阅读更多
素数
发布于: 2021-02-17 更新于: 2021-04-28 分类于: OI

数论的基础(?)

阅读更多
快速乘
发布于: 2021-02-12 更新于: 2021-04-28 分类于: OI

快速龟速乘。

阅读更多
快速幂
发布于: 2021-02-07 更新于: 2021-04-28 分类于: OI

经典二进制分治。

阅读更多
扩展欧几里得算法 Extended Euclidean algorithm, extgcd
发布于: 2021-02-07 更新于: 2021-04-28 分类于: OI

扩展欧几里得,用于解同余方程。

阅读更多
欧几里得算法,辗转相除法 Euclidean algorithm, gcd
发布于: 2021-02-07 更新于: 2021-04-28 分类于: OI

GCD… 应该没人不会吧……

阅读更多