膜拜国际特级大师 SMTwy
膜拜国际特级大师 SMTwy
膜拜国际特级大师 SMTwy
膜拜国际特级大师 SMTwy
膜拜国际特级大师 SMTwy
推歌：ダーリン (Darling) - MARETU .
约定素数集为 \(\mathbb P\)，\(p_i\) 为第 \(i\) 个素数 .
基本定义
定义偏序集 \((R_1,\le_1)\) 和 \((R_2,\le_2)\) 的直积（direct product）\((R,\le)=(R_1,\le_1)\times(R_2,\le_2)\) 满足
\[\begin{aligned}&R=R_1\times R_2\\&(x,y)\le(x',y')\iff(x\le_1 x')\land(y\le_2 y')\end{aligned} \]
考虑偏序集 \((\mathbb Z_+,\mid)\)（整除），根据唯一分解定理，它可以被分解为若干个线性序（或者叫全序）的直积 .
对于第 \(i\) 个素数 \(p_i\)，定义 \(L_i=\{p_i^x\mid x\in\mathbb N\}\)，那么「整除偏序集」就可以表示为
\[(\mathbb Z_+,\mid)=\prod_{i\ge 1}(L_i,\le) \]熟知 Mo"bius 函数 \(\mu\) 在线性序 \((R,\le)\) 上的表现：
\[\mu(x,y)=\begin{cases}1&x=y\\-1&x+1=y\\0&\text{otherwise.}\end{cases}\qquad(\text{where }x\le y) \]其中 \(x=y\iff x\le y\land y\le x\)，\(x+1=y\iff (\forall z\neq x,y:z<x\lor y<z)\) .
根据定义可以得知，偏序集直积后，\(\delta,\zeta,\mu\) 的表现均为乘积 .
那么展开 Mo"bius 函数关于线性序直积的观察，可以得到
\[\begin{aligned}\mu(x,y)&=\prod_{i\ge 1}\mu_{L_i}(x,y)\\&=\prod_{i\ge 1}\begin{cases}1&e_i=f_i\\-1&e_i+1=f_i\\0&\text{otherwise.}\end{cases}\\&=\begin{cases}0&y/x\text{ is square-free number.}\\(-1)^{\omega(y/x)}&\text{otherwise.}\end{cases}\end{aligned}\qquad(\text{where }x\mid y) \]其中 \(\displaystyle x=\prod_{i\ge 1}p_i^{e^i},\displaystyle y=\prod_{i\ge 1}p_i^{f_i}\) 是 \(x,y\) 的唯一分解，\(\omega(n)\) 为 \(n\) 的不同素因子数量 .
这其实已经导出了我们熟知的 Mo"bius 函数，根据上式可知，\(\mu(x,y)=\mu\left(1,\dfrac yx\right)\)，那么令 \(\mu(x)=\mu(1,x)\)，使用 Mo"bius 反演，可以得到
\[f(n)=\sum_{d\mid n}g(d)\iff g(n)=\sum_{d|n}\mu\left(\dfrac{n}{d}\right)f(d) \]这就是 OI 中常见的 Mo"bius 反演 .
以上内容的探讨已经广为人知，下面来讨论它的一个应用 .
春季测试 2023 幂次
问 \([1,n]\) 中，有多少整数 \(x\) 能表示为 \(x=a^b\) 的形式，其中 \(a\ge 1,b\ge k\) .
\(1\le n\le 10^{18}\)，\(1\le k\le 100\) .
首先特判 \(k=1\)，那么问题变为 \(k=2\) 的答案 . 令 \(f(n)\) 表示 \([1,n]\) 能表示为 \(x=a^b\) 形式的整数 \(x\) 个数，其中 \(a\ge 1,b\ge 2\)，那么答案可以简单表述为
\[f(n)-\sum_{i=2}^{k-1}f(\lfloor\sqrt[i]{n}\rfloor) \]于是只需要快速计算 \(f\) .
发现一个数可能被多次计算，自然考虑容斥，观察到 \(a^{bx}=(a^b)^x\)，那么对指数容斥即可 .
偏序集的容斥或许就是对于每个「前缀」的集合做朴素容斥原理（「前缀」大概就是 \(\{y\mid y<x\}\) 吧），于是令 \(S=\{x\mid \mu(x)\neq 0\}\) 即 square-free number 集，在 \((S,\mid)\) 上容斥，不在 \(S\) 内的数不产生贡献 .
考虑把 \((S,\mid)\) 拆解为线性序的直积，根据直觉，考虑设计线性序的容斥系数然后乘起来得到 \((S,\mid)\) 的容斥系数 .
然而线性序的容斥系数是显然的，对于元素 \(x\)，如果恰有 \(z\) 个 \(y\) 满足 \(y<x\)，那么容斥系数 \(I(x)=(-1)^y\)（直接考虑对于每个「前缀」的集合做朴素容斥原理）.
那么答案的容斥系数就是
\[\begin{aligned}I(x)&=-\prod_{i\ge 1}I_{L_i}(i)\\&=-\prod_{i\ge 1}(-1)^{e_i}\\&=-(-1)^{\omega(x)}\end{aligned} \]（负号是为了算上本身的贡献）
其中 \(\displaystyle x=\prod_{i\ge 1}p_i^{e_i}\) 是 \(x\) 的唯一分解 .
结合一下即可得到总的容斥系数就是 \(I(x)=-[x\in S](-1)^{\omega(x)}=-\mu(x)\) .
这样就能算出答案了，复杂度是 \(\Theta(k\log n)\) .
好像 GCD Matrices 的问题也能用相关做法解决，不过我没详细了解了 .
我也不知道我在写啥，要是看不懂大概是我写挂了可以评论区发一下 .
这个设计好像在 \(\N_+\) 更自然一点，\(S\) 上有点硬凑的感觉了 .
标签：mu,le,闲话,容斥,mid,2023.3,ge,prod From： https://www.cnblogs.com/CDOI-24374/p/17195733.html