数论 / 比赛日志 超-4运算在 Z/nZ 上的收敛性 – 欧拉函数与扩展欧拉定理 扩展欧拉定理揭示了对于任意模数 nnn，有 ab mod n={ab,b<φ(n)ab mod φ(n)+φ(n),otherwise. a^b\bmod n=\begin{cases} a^b,&b<\varphi(n)\\ a^{b\bmod \varphi(n)+\varphi(n)},&\text{otherwise} \end{cases}. abmodn={ab,abmodφ(n)+φ(n),b<φ(n)otherwise. 我们又知道若分解质因数 x=∑picix=\sum p_i^{c_i}x=∑pici，则 φ(x)=x∏(pi−1)/pi\varphi(x)=x\prod (p_i-1)/p_iφ(x)=x∏(pi−1)/pi。则若 x>1x>1x>1，若 2∣x2\mid x2∣x，φ(x)≤x/2\varphi(x)\leq x/2φ(x)≤x/2；否则，2∣φ(x)2\mid\varphi(x)2∣φ(x)。记 φ(k)(x)=φ(φ(⋯φ(⏟k layersx)⋯ ))\varphi^{(k)}(x)=\underbrace{\varphi(\varphi(\cdots\varphi(}_{k\text{ layers}}x)\cdots))φ(k)(x)=k layersφ(φ(⋯φ(x)⋯))，则 O(logn)\newcommand\bigO{\operatorname{O}}\bigO(\log n)O(logn) 级别的 kkk 就能使其收敛到 111。 因此对于 Z/nZ\mathbb{Z}/n\mathbb{Z}Z/nZ 上的超-4运算 a1a2a3⋰a_1^{a_2^{a_3^{⋰}}}a1a2a3⋰，结合扩展欧拉定理得到，在指数塔的 O(logn)\bigO(\log n)O(logn) 层就将得到 mod φ(1)+φ(1)≡1\bmod\varphi(1)+\varphi(1)\equiv 1modφ(1)+φ(1)≡1 的指数。从而它是收敛的。 （更多…） More 2023年11月30日
数论 / 比赛日志 MOCK quasi-PTS 20230209 日志 近一个月来第一次赛时通过一道题。真是可喜可贺。 A – 单调 一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。 题意简述 给定长为 n (n≤105)\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)n (n≤105) 的序列 ⟨ai⟩,ai∈{1,2,3}\langle a_i\rangle,a_i\in\{1,2,3\}⟨ai⟩,ai∈{1,2,3}。匹配尽可能多的子序列，每个子序列均为 ⟨1,2,3⟩\langle 1,2,3\rangle⟨1,2,3⟩ 或 ⟨3,2,1⟩\langle 3,2,1\rangle⟨3,2,1⟩，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…） More 2023年2月9日
