话说我的数论和数学已经不够我现在用了，随便做点题都要推式子，不如先学一下有什么要学的———方便做题。
数论基础
首先必然是余数。
余数在数论中出现的频次（也许）最多了。
带余除法
（ 是常数，一般不考虑 正负，以下也不考虑）
一般取余都会带入 ，即 。
还有一种特殊余数（绝对最小余数），，即 （话说要取整吗 数论基础 - OI Wiki (oi-wiki.org) 这里没有取整）
性质
唯一性：这个 在区间内唯一。
充分性：连续取 个整数构成的剩余系是完全的。
最大公约数和最小公倍数
没什么好讲的；
辗转相除法 / 辗转相减法：欧拉定理；
高精度 gcd / lcm：
要让最终时间复杂度为 ，
辗转相减法 + 二的因数优化：
高精度加减 & 高精除单精： 。
注意！
如果使用辗转相减法会使算法变为 （高精度除法为 ）。
高精度送分题： P2152 [SDOI2009] SuperGCD
1
2
| import math
print(math.gcd(int(input()),int(input())))
|
算数基本定理
（没听过，但显然）
引理：设 是素数，，那么 和 至少有一个成立。
定理：设正整数 ，必有：
其中 是素数，且唯一（不计次序）。
以及，合并相同的 ，得到因式分解式：
同余
表示 。
式中的 是 对模 的剩余，这个概念与余数完全一致。通过限定 的范围，相应的有 对模 的最小非负剩余、绝对最小剩余、最小正剩余。
性质（抄过来啦）
From OI-Wiki
- 自反性：。
- 对称性：若 ，则 。
- 传递性：若 ，则 。
- 线性运算：若 则有：
- 若 , 则 。
- 若 ，则当 成立时，有 。
- 若 ，则当 成立时，有 。
- 若 ，则当 成立时，有 。若 能整除 及 中的一个，则 必定能整除 中的另一个。
数论函数
OI Wiki (oi-wiki.org)：「数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。」
积性函数
重点——
定义
若函数（数论函数） 满足 ， 都有 ，那么 为积性函数。
若对于 都有 ，那么 为完全积性函数。
性质
积性函数的传递性：
若 与 都为积性函数，那么以下函数也是积性函数：
应用：
设 ，（此处 是质数吗？分解质因式）
若 为积性函数，则有 。
若 为完全积性函数，则有
其中第二条与第一条区别在于乘方的位置！
例子（常用数论函数 /se
单位函数：；
恒等函数： （；
常数函数：；
除数函数：， 是常数。 时函数记为 ， 时记为 。
欧拉函数：。
莫比乌斯函数：，其中 表示 的本质不同质因子个数：加性函数
。[^ref1]
加性函数
此处加性函数指数论上的加性函数 (Additive function)。对于加性函数 ，当整数 互质时，均有 。 应与代数中的加性函数 (Additive map) 区分。
莫比乌斯反演
前置知识：数论分块、狄利克雷卷积。
狄利克雷卷积
定义
设 为数论函数。
或
（感觉后面那个式子更好看 /kk）
More?
可以形象的理解为 将 分为两个数乘积，将两个数分别带入 ，乘积之和为结果。
逆
结论：
性质
如果 是积性函数，则 也是积性函数；
其实这个性质在积性函数性质章节提到过——
是在狄利克雷卷积下，它长这样：。
其他性质看这里——算法学习笔记(35): 狄利克雷卷积 - 知乎 (zhihu.com)
莫比乌斯函数
定义[^ref2]
为莫比乌斯函数，定义为
详细解释一下：
令 ，其中 为质因子，。上述定义表示：
-
时，；
-
对于 时：
-
当存在 ，使得 时，，也就是说只要某个质因子出现的次数超过一次， 就等于 ；
-
当任意 ，都有 时，，也就是说每个质因子都仅仅只出现过一次时，即 ， 中个元素唯一时， 等于 的 次幂，此处 指的便是仅仅只出现过一次的质因子的总个数。
性质
，。其中 。
证明：二项式定理。
反演性质
莫比乌斯变换
设 。
形式 1
若 ，则
。
莫比乌斯变换 可以看作 与 做卷积：。
卷积：
已知 ，证明：。
。
，
设 ：
设 ：
根据莫比乌斯函数的定义，
这条式子在只有 的时候才会对式子有影响。
总共 个因数，所以
所以 。
所以 。
证毕。
形式 2
，那么 。
例题
题目的要求：
变形：
再变：
令 ，在 时重复，所以 。
再变：
观察到中间的 可以前缀和掉，
做 的前缀和然后爆搜即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int N, prime[MAXN], vis[MAXN], phi[MAXN], tot;
void GetPhi(int N) {
vis[1] = phi[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <cstdio>
#include <cstring>
#include <vector>
#define gc getchar()
template<typename T>
void read(T &r) {
r = 0; static char ch, last;
ch = gc, last = 'z';
while (ch < '0' || ch > '9') last = ch, ch = gc;
while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
r = (last == '-') ? -r : r;
}
template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) {
read(arg);
read(arg_left...);
}
#define int long long
#define MAXN 11451419
int N, prime[MAXN], vis[MAXN], phi[MAXN], tot;
void GetPhi(int N) {
vis[1] = phi[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i]) prime[++tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if (!(i % prime[j])) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
for (int i = 1; i <= N; i++) {
phi[i] += phi[i - 1];
}
}
signed main() {
int n, ans = 0;
read(n);
GetPhi(n + 57);
for (int i = 1; ; i++) {
if (prime[i] > n) break;
ans += phi[n / prime[i]] * 2 - 1;
}
printf("%lld\n", ans);
return 0;
}
|
据说 LuoguP9157 逝莫反，等 WBWYX 大蛇做出来去请教一下。
Update by 2023/03/20
[^ref1]: 数论基础 - OI Wiki
[^ref2]: 莫比乌斯反演 - OI Wiki
[^ref3]: 浅谈积性函数的线性筛法 - 自为风月马前卒 - 博客园