正睿19暑期B班DAY7 数论

洛谷今日份：宜打chunithm（您虹了），sdvx（您暴了）

今日又是课件非常丰富份，本文仅作批注

首先要理解群，环，域的概念（这个会再提一次）

几个代数结构

群是一个集合加上一个运算

满足封闭性、结合律、有单位元、有逆元的二元运算

环定义了两种运算的非空集合，满足加法分配律和乘法结合律、分配律

幺环有单位元的环

域设F是一个有单位元e1（≠0）的交换环（满足乘法交换律的幺环）。如果F中每个非零元都可逆，称F是一个域。

也可以理解为能够做四则运算，对于四则运算得到的结果还在域内（封闭）的幺环

有助于理解并防止本文过长的链接

质因子分解

素性测试

试除法
Miller-Rabin

板子等到血书要到了再补，没有就补一个自己的小菜板

AKS算法右转某度百科

质因子分解

试除法，复杂度 O((sqrt n))，太慢了。
Pollard’s Rho，期望复杂度 O((^{4}sqrt{n} log n))，又名启发式分解。

数论

GCD & ExGCD

我相信你们已经完全会了

类欧几里得算法

解决类似于这样的问题

[solve(n, A, B, C) = sum_{i = 1}^{n} lfloor frac{Ai + B}{C} floor ]

把它移项一下之后递归，具体见课件

关于课件里有几个名词问了一下数竞玩家：

hjmmm:环是什么？

念去去:环是一个定义了两种运算的群，满足加法分配律和乘法结合律、分配律。就是说在环这个范围内，+运算和×运算都是可以进行的。环具体是什么要具体问题具体分析。如果是mod5的，那么就是0-4。

hjmmm:明白辽。。emm那群是什么

念去去:就是进行某一种运算的范围。对于不同运算规则，群是可能不相同的。比如同余运算的群一般是整数

hjmmm:明白辽。。emm什么叫模合数的环？它和模质数的有什么区别？

念去去:膜质数简单，膜质数可以用更多的定理。Lucas定理威尔逊定理之类的。对于有的概率运算膜合数的结果和膜质数的不一样。这个我也不太清楚了。。。

hjmmm:好的感谢vq

中国剩余定理 CRT&ExCRT

这里放一下r爷举的ExCRT的栗子

(x = 3 (mod 12), x = 7 (mod 8))

(x = 3 (mod 4))

(x = 4k + 3 mod(lcm(12, 8)))

(k = 0 (mod 3), k = 1 (mod 2))

把k解出来之后把两个方程合并成一个mod(lcm(p1, p2))的方程

费马小定理

p 是质数，则 (a^p ≡ a (mod p))

欧拉定理

p > 1，a, p 互质，则 (a^{ϕ(p)} ≡ 1 (mod p))

缩系：和x互质的所有数的集合

扩展欧拉定理

$p > 1，n ≥ ϕ(p) 存在 a^n ≡ a^{n mod ϕ(p)+ϕ(p)} (mod p)

离散对数问题

BSGS

求(A^x ≡ B (mod C))

ExBSGS

A, B, C一起除以gcd(A, C)

原根相关

循环群：指群可以由一个元素生成：(G = x, x^2, x^3 ...)。

阶：满足 (x^d = 1)的最小正整数 d。记为 ord(x)。

$x^m = 1 $当且仅当 (ord(x)|m)。

模素数 p 的剩余类构成一个有限域。

模 m 意义下与 m 互质的元素组成缩系，大小为 ϕ(m)。

原根：能生成缩系的元素，即 (x^i) 两两不同(（0 ≤ i < ϕ(m)))的 x。原根不一定存在。事实上，当且仅当 (m = 2, 4, p^k,2∗p^k) 时，模 m 缩系的原根存在。p 是任意奇质数。

Fact: 设 a 的阶是 m，(d|m)，则 (a^d) 的阶是 (frac{m}{d}) 。

Fact: 设 a 的阶是 m，b 的阶是 n，则必存在一个数，阶是 (lcm(n, m))

Fact: n 个元素的循环群的生成元个数为 ϕ(n)。

好，相信看到这里你已经懵了

宛转表达：这个时候我们需要拉一个数竞党让他来证一遍

直接说明：咕咕咕

二次剩余

((frac{a}{p}))表示 a 是模 p 域下的二次剩余，-1 表示是二次非剩余

p.s. LeTaX打法：(frac{a}{p})

计算：((frac{a}{p}) = a^{frac{p - 1}{2}} (mod p))

二次互反律：((frac{p}{q})(frac{q}{p})=(-1)^{frac{(p-1)(q - 1)}{4}})

二次剩余计算方法：原根法 / Cipolla算法

Cippolla：

rand一个a使得(a^2 - n)是二次非剩余

设(w = sqrt{a^2 - n})，(x + yw)形成一个域（(x + yw)是mod P域的扩域）

二次剩余解为((a + w)^{frac{p + 1}{2}})

关于证明，注：mod P下有性质 ((a + b)^P = a^P + b^P (mod P))

关于证明((a + w)^{frac{p + 1}{2}})不含(w)项，注：((a^2 - w) = frac{n}{y^2})

跳跳棋

link

注意按照规则，一个状态只有三种转移（向里跳，中间棋子向左跳或向右跳）

这样的话我们把第一种情况作为父亲，后两种作为儿子

然后对于(a, b, c)，如果有(b - a > c - b)

那么(a, b, c)到父亲的距离就是(lfloor frac{b - a}{c - b} floor)
Power Tower

(a_{l}^{a_{l + 1}^{...^{a_{r}}}})这个东西直接暴力就好啦

只要下面变成1了就不用乘了
Chinese Leftover Ⅱ

(a_1 + (a_2 - a_1) * p_1 * inv(p_1, p_2) （mod p_1p_2))

(F(i , j) = F(i - 1, j) + (a_2 - a_1) * inv(p1, p2) mod p2 * p1)

感觉别的题ppt写的很清楚啊

数论函数

从这里开始，一定要手推！一定要手推！一定要手推！

hjmmm:陪域是什么qvq

"数论函数：定义域为正整数集，陪域为复数域的函数。"

念去去:值域是陪域的一部分，值域是定义域映射到的陪域的那部分。

hjmmm:那陪域有什么用

念去去:人家没告诉你映射，比如说从整数集映到复数集，这个“复数集”就是陪域，相当于把我们高中习惯的叫法更严谨了。

hjmmm:所以陪域只要包含值域，是什么都行咯？

念去去:最起码。。。最起码作业帮是这个意思。所以陪域这个东西在这里就有点鸡肋了。。。

两个数论函数的迪利克雷卷积：（符号为*）

[(f*g)(n)=sum_{d|n}f(d)g(frac{n}{d}) ]

满足：

交换律：f ∗ g = g ∗ f

结合律：(f ∗ g) ∗ h = f ∗ (g ∗ h)

分配律：f ∗ (g + h) = f ∗ g + f ∗ h

单位元：

若 f**, g 是积性函数则 f ∗ g 也是积性函数。

一些性质：

若 g = f ∗ 1，则 f = g ∗ µ

这个主要是用到(sum_{d | n} mu(d) = sum_{S subset T} (-1)^{|S|} = sum_{i = 0}^{n} binom{n}{i}(-1)^i = (1-1)^n = 0)

所以(sum_{d | n} mu(d) = [n = 1])

同时(mu * 1 = epsilon)（为了方便各位，(epsilon)的LaTeX是epsilon）

(epsilon)函数是单位元，有f ∗ ϵ = f

于是我们收获：

(σ_k = Id_k ∗ 1，Id_k = σ_k ∗ µ)

注：(σ_k)(n)表示n的约数的k次方之和，(Id(n))表示n的k次方

(Id_1 = ϕ ∗ 1，ϕ = Id_1 ∗ µ)

注：(Id_1) = {1, 2, 3, ..., k}

莫比乌斯反演和杜教筛

真的打公式快。死。了。

以后再填坑qvq

Min25筛

如果有不理解的地方可以参考：

对于ppt中的Part1 Part2 分别求解了质数范围和全部范围的积性函数前缀和
那个(T(n))是要求的积性函数
Part1中的F函数其实筛到最后，对于每一个j，只需要F(i, j)

其中i为最小的i使得(p_i^2 > n)

Part2中的F(i)默认忽略了第一维
注意F(i, j)的第二维只有(sqrt{n})级别

这(k*sqrt{n})个数（k为常数）中，包含了1到(sqrt{n})

所以Part1转移式中那个"(F(i - 1, p_{i - 1}))"不必担心不在范围内
Part1的F是从小到大转移的 Part2中的S是从大到小转移的
Part2答案式中S(1, n) + 1最后的加一加的是T(1)

（积性函数T(1) = 1）
Part2递推式中(T(p_{j}^{e+1}))只是表示指数从2开始累计

因为(T(p_j))已经在质数中累计过了