整除分块和狄利克雷卷积没啥说的。
规定莫比乌斯函数 \(\mu(i)\) 满足 \(i\) 被表示为 \(x\) 个单个质因子的积时返回值为 \((-1)^x\)。其余时为 \(0\)，\(\mu(1)=1\)。
有重要性质
\[\sum_{d|n}\mu(d)=[n=1] \]证明：不妨设
\[n=\prod^m p_i^{a_i},n'=\prod^m p_i \]则应满足
\[\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d) \]后面一部分的每个 \(\mu(d)\) 都是有返回值的，\(n'\) 有保证了质因子不同所以对 \(x=i\) 个质因子的情况有 \(\binom{m}{i}\) 种取法，返回值全为 \((-1)^i\)
二项式定理：
\[\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=1}^m\binom{m}{i}(-1)^i=(1+(-1))^m=1 \]然后好了。
有一个很典的应用，即莫反：
\[[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)=\sum_{d=1}^n[d|i][d|j]\mu(d) \] \[Ans=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)\in prime]\\ \]\[=\sum_{d=1}^n[d\in prime]\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]\\ \]\[=\sum_{d\in prime}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{x=1}^{\frac{n}{d}}[x|i][x|j]\mu(x)\\ \]\[=\sum_{d\in prime}\sum_{x=1}^{\frac{n}{d}}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor \]这种多变量难以整除分块就设 \(T=dx,x=\frac{T}{d}\)
。原式变为
然后前半整除分块后半调和级数预处理，有的时候后半满足积性函数，可以直接在线筛的时候处理出来。复杂度 \(O(\sqrt n)\)
其他题都大同小异，不多说了。
P3704
为啥学校oj写东西不显示latex？？
就是说，把求和改成指数形式。
\[Ans=\prod_{i=1}^n\prod_{j=1}^mf(gcd(i,j))\\ \]\[=\prod_{d=1}^nf^{\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{j}{m}\rfloor}[gcd(i,j)=d]}(d)\\ \]\[=\prod_{d=1}^nf^{\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}(d) \]设 \(T=dx,x=\frac{T}{d}\)。
\[Ans=\prod_{d=1}^nf^{\sum_{d|T}^n\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor}(d)\\ \]\[=\prod_{T=1}^n\prod_{d|T}f^{\mu(\frac{T}{d}\lfloor\frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor)}(d)\\ \]\[=\prod_{T=1}^n(\prod_{d|T}f^{\mu(\frac{T}{d})}(d))^{\lfloor\frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor} \]设 \(F(x)=\prod_{d|T}f^{\mu(\frac{T}{d})}(d)\)，可以调和级数复杂度算出来。
\[Ans=\prod_{T=1}^nF^{\lfloor\frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor}(T) \]相当于把数论分块挪到指数上，想一下就是维护前缀积算的时候拿逆元和快速幂算。
标签：lfloor,frac,sum,rfloor,mu,莫反,prod From： https://www.cnblogs.com/Claimo0611/p/18628264