MtOI2019 幽灵乐团

我来吃屎了，哈哈啊哈哈哈啊哈哈啊哈！！！！！！！！！

发现对于题目要求的式子：

$\dfrac{\text{lcm}(i,j)}{\gcd(i,k)}=\dfrac{i\times j\div\gcd(i,j)}{\gcd(i,k)}=\dfrac{i\times j}{\gcd(i,k)\times \gcd(i,j)}$

那么考虑把这个式子剥离开，得到：

$\left\{\begin{matrix}P_1=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C i^{f(type)} \\P_2=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C j^{f(type)} \\P_3=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\gcd(i,j)^{f(type)} \\P_4=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C \gcd(i,k)^{f(type)} \\ans=\dfrac{P_1\times P_2}{P_3\times P_4}\end{matrix}\right.$

$type=0$

先简化 $P_1,P_2$：

$\left\{\begin{matrix}P_1=(\prod\limits_{i=1}^A i)^{B\times C}= (A!)^{B\times C}\\P_2=(\prod\limits_{j=1}^B)^A\times C{=(B!)^{A\times C}}\end{matrix}\right.$

容易想到：

$\prod\limits_{i=1}^{A}\prod\limits_{j=1}^B\gcd(i,j)=\prod\limits_{d=1}^Ad^{\sum _{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d]}$

考虑怎么把指数上的式子反演掉，设：

$f(n)=\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=n]$

$F(n)=\sum\limits_{n\mid k}f(k)=\lfloor\dfrac{a}{n}\rfloor\times \lfloor\dfrac{b}{n}\rfloor$

对于 $F(n)$，容易理解如果 $gcd(i,j)\mid n$，那么 $i\mid n$，$j\mid n$。

因为 $[1,a]$ 中有 $\lfloor\dfrac{a}{n}\rfloor$ 个，$[1,b]$ 中有 $\lfloor\dfrac{b}{n}\rfloor$ 个且两两组合都可以，所以 $F(n)=\lfloor\dfrac{a}{n}\rfloor\times \lfloor\dfrac{b}{n}\rfloor$。

那么对这个式子进行莫比乌斯反演，得到：

$f(n)=\sum\limits_{n\mid k}\mu(\lfloor\dfrac{k}{n}\rfloor)\times F(k)$

设 $t=\lfloor\dfrac{k}{d}\rfloor$，那么就有：

$f(d)=\sum\limits_{t=1}^{\min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)} \mu (t)\times \lfloor\dfrac{a}{td}\rfloor\times \lfloor\dfrac{b}{td}\rfloor$

也就是：

$\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=d]=\sum\limits_{t=1}^{\min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)} \mu (t)\times \lfloor\dfrac{a}{td}\rfloor\times \lfloor\dfrac{b}{td}\rfloor$

发现就是「HAOI2011」Problem b。

带回原式，得到：

$\prod\limits_{i=1}^Ad^{\sum\limits_{t=1}^{\min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)} \mu (t)\times \lfloor\dfrac{a}{td}\rfloor\times \lfloor\dfrac{b}{td}\rfloor}$

设 $T=dt$，把 $td$ 一样的放在一起考虑，得到：

$\prod\limits_{T}^{\min(A,B)}(\prod\limits_{d\mid T} d^{\mu(T/d)})^{\frac{A}{T}\times \frac{B}{T}}$

枚举 $d$，找到 $T$ 把答案加上去，最后算次方再乘起来，时间复杂度为 $O(n\log n)$。

$type=1$

考虑怎么求解：

$\prod\limits_{i=1}^{A}\prod\limits_{j=1}^B\prod\limits_{k=1}^C i^{i\times j\times k}$

把后面提出来，得到：

$\prod\limits_{i=1}^A i^{\dfrac{j\times (j-1)\times k\times (k-1)}{4}}$

需要用欧拉降幂。

考虑后面怎么推：

$\prod\limits_{i=1}^{A}\prod\limits_{j=1}^B\prod\limits_{k=1}^C \gcd(i,j)^{i\times j\times k}$

把 $\prod\limits_{k=1}^C$ 拿出来，得到：

$(\prod\limits_{i=1}^A\prod\limits_{j=1}^B \gcd(i,j)^{i\times j})^{\dfrac{k\times(k+1)}{2}}$

类似于 $type=0$ 的时候，我们可以发反演得到：

$\prod\limits_{T=1}^{\min(A,B)}(\prod\limits_{d\mid T} d^{\mu(T/d)})^{T^2\times S(A/T)\times S(B/T)}$

其中 $S(x)=\dfrac{x\times(x-1)}{2}$。

$type=2$

对于指数的情况，直接开 $\log$。

得到：

$\sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^C\gcd(i,j,k)\times \ln(\dfrac{\text{lcm}(i,j)}{\gcd(i,k)})$

考虑证明一下，有欧拉反演：

$n=\sum\limits_{d\mid n}\varphi(d)$

那么：

$\gcd(i,j,k)=\sum\limits_{d\mid \gcd(i,j,k)} \varphi(d)$

带入，得到：

$\sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^C\sum\limits_{d\mid \gcd(i,j,k)} \varphi(d)\times \ln(\dfrac{\text{lcm}(i,j)}{\gcd(i,k)})$

令 $i\gets di,j\gets dj,k\gets dk$，得到：

$\sum\limits_{d=1}^{\min(A,B,C)}\sum\limits_{i=1}^\frac{A}{d}\sum\limits_{j=1}^{\frac{B}{d}}\sum\limits_{k=1}^{\frac{C}{d}} \varphi(d)\times \ln(\dfrac{\text{lcm}(id,jd)}{\gcd(id,kd)}$

把 $\varphi(d)$ 拿出来，得到：

$\sum\limits_{d=1}^{\min(A,B,C)}\varphi(d)\sum\limits_{i=1}^\frac{A}{d}\sum\limits_{j=1}^{\frac{B}{d}}\sum\limits_{k=1}^{\frac{C}{d}} \ln(\dfrac{\text{lcm}(id,jd)}{\gcd(id,kd)}$

把后面的 $d$ 消了：

$\sum\limits_{d=1}^{\min(A,B,C)}\varphi(d)\sum\limits_{i=1}^\frac{A}{d}\sum\limits_{j=1}^{\frac{B}{d}}\sum\limits_{k=1}^{\frac{C}{d}} \ln(\dfrac{\text{lcm}(i,j)}{\gcd(i,k)}$

那么整体把 $\ln$ 拿掉得到：

$\prod\limits_{d=1}^{\min(A,B,C)}(\prod\limits_{i=1}^\frac{A}{d}\prod\limits_{j=1}^{\frac{B}{d}}\prod\limits_{k=1}^{\frac{C}{d}} \dfrac{\text{lcm}(i,j)}{\gcd(i,k)})^{\varphi(d)}$

发现里面就是 $type=0$ 的情况，做完了。

实现

一些数组的意义：

$f_1(n)=\prod\limits_{T=1}^n\prod\limits_{i\mid T}i^{\mu (\frac{T}{i})}$

$f_2(n)=\prod\limits_{T=1}^n(\prod\limits_{i\mid T}i^{\mu(\frac{T}{i})})^{T^2}$

$phi(n)=\sum\limits_{i=1}^n \varphi(i)$

$F(A,B)=\prod\limits_{T=1}^{\min(A,B)}(\prod\limits_{d\mid T} d^{\mu(T/d)})^{S(A/T)\times S(B/T)}$

$G(A,B)=\prod\limits_{T=1}^{\min(A,B)}(\prod\limits_{d\mid T} d^{\mu(T/d)})^{T^2\times S(A/T)\times S(B/T)}$

SDOI2015 约数个数和

感性理解，发现：

$d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j}[\gcd(x,y)=1]$

所以原式求解的就是：

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$

显然 $i,j$ 对答案并没有实际的影响，把 $x,y$ 替换为 $i,j$。

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lfloor\dfrac{n}{i}\rfloor\times \lfloor\dfrac{m}{j}\rfloor\times [\gcd(i,j)=1]$

套路的，设：

$f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lfloor\dfrac{n}{i}\rfloor\times \lfloor\dfrac{m}{j}\rfloor\times [\gcd(i,j)=x]$

$g(x)=\sum\limits_{x\mid n} f(n)=\sum\limits_{i=1}^{\frac{n}{i}}\sum\limits_{j=1}^{\frac{m}{j}} \lfloor\dfrac{n}{ix}\rfloor\times\lfloor\dfrac{m}{jx}\rfloor$

所以反演得到：

$f(p)=\sum\limits_{p\mid x}\mu(\dfrac{x}{p}) g(x)=\sum\limits_{p\mid x} \mu(\dfrac{x}{p})\sum\limits_{i=1}^{\frac{n}{i}}\sum\limits_{j=1}^{\frac{m}{j}} \lfloor\dfrac{n}{ix}\rfloor\times\lfloor\dfrac{m}{jx}\rfloor$

所以：

$f(1)=\sum\limits_{t=1}^{\min(n,m)}\mu(t)\sum\limits_{i=1}^\frac{n}{t}\sum\limits_{j=1}^\frac{m}{j}\lfloor\dfrac{n}{it}\rfloor\times \lfloor\dfrac{m}{jt}\rfloor$

P1829 Crash的数字表格

套路的转化 $\text{lcm}$，得到：

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\dfrac{i\times j}{\gcd(i,j)}$

那么枚举 $\gcd(i,j)$ 的值：

$\sum\limits_{d=1}^{\min(n,m)}d\times \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\times i\times j$

不经典的反演：

$f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[\gcd(i,j)=d]\times i\times j$

$g(d)=\sum\limits_{d\mid n} f(n)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor\times$

byd，反演不出来，还需要继续简化，有一个暴强的性质：

$\sum\limits_{d\mid n}\mu(d)=[n=1]$

那么得到：

$\sum\limits_{d=1}^{\min(n,m)}d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\frac{m}{d}} \sum\limits_{x\mid \gcd(i,j)}\mu(x)\times ij$

简化得到：

$\sum\limits_{d=1}^{\min(n,m)}d\sum\limits_{x=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\times[x\mid \gcd(i,j)]$

那么继续 $i\gets ix,j\gets jx$，得到：

$\sum\limits_{d=1}^{\min(n,m)} d\sum\limits_{x=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{dx}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{dx}\rfloor} ij\times x^2$

拿出来得到：

$\sum\limits_{d=1}^{\min(n,m)}d\sum\limits_{x=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(x)\times x^2(\sum\limits_{i=1}^{\lfloor\frac{n}{dx}\rfloor}i)\times(\sum\limits_{j=1}^{\lfloor\frac{m}{dx}\rfloor} j)$

那么设 $S(x)=\dfrac{x\times(x+1)}{2}$，则：

$\sum\limits_{d=1}^{\min(n,m)}d\sum\limits_{x=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(x)\times x^2\times S(\lfloor\dfrac{n}{dx}\rfloor)\times S(\lfloor\dfrac{m}{dx}\rfloor)$

那么设 $T=dx$，则：

$\sum\limits_{T}^{\min(n,m)} S(\lfloor\dfrac{n}{T}\rfloor)\times S(\lfloor\dfrac{m}{T}\rfloor)\sum\limits_{T=dx}d\times x^2\times\mu(x)$

那么就得到了：

$\sum\limits_{T}^{\min(n,m)}S(\lfloor\dfrac{n}{T}\rfloor)\times S(\lfloor\dfrac{m}{T}\rfloor)\times T\times \sum\limits_{x\mid T}\mu(x)\times x$

关于实现：

$f(T)=T\times \sum\limits_{x\mid T}\mu(x)\times x$

预处理 $f(T)$，其他分块即可。

P2257 YY的GCD

$\sum\limits_{p\in\text{prime}} \sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=p]$

把 $p$ 拿出来：

$\sum\limits_{p\in\text{prime}}\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(i,j)=1]$

反演：

$f(n)=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[\gcd(i,j)=n]$

$g(d)=\sum\limits_{d\mid n} f(n)=\lfloor\dfrac{N}{d}\rfloor\times \lfloor\dfrac{M}{d}\rfloor$

得到：

$f(n)=\sum\limits_{n\mid d} \mu(\dfrac{d}{n})\times g(d)=\sum\limits_{n\mid d}\mu(\dfrac{d}{n})\times \lfloor\dfrac{N}{d}\rfloor\times \lfloor\dfrac{M}{d}\rfloor$

所以：

$f(1)=\sum\limits_{d=1}^{\min(N,M)}\mu(d)\times \lfloor\dfrac{N}{d}\rfloor\times \lfloor\dfrac{M}{d}\rfloor$

因为 $N=\lfloor\frac{n}{p}\rfloor$，$M=\lfloor\frac{m}{p}\rfloor$，所以带入得到：

$\sum\limits_{p\in\text{prime}}\sum\limits_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\times \lfloor\dfrac{n}{pd}\rfloor\times \lfloor\dfrac{m}{pd}\rfloor$

设 $T=pd$，那么：

$\sum\limits_{p\in\text{prime}}\sum\limits_{T=1,p\mid T}^{\min(n,m)}\mu(\dfrac{T}{p})\times \lfloor\dfrac{n}{T}\rfloor\times\lfloor\dfrac{m}{T}\rfloor$

那么改变一下顺序：

$\sum\limits_{T=1}^{\min(n,m)}\lfloor\dfrac{n}{T}\rfloor\times\lfloor\dfrac{m}{T}\rfloor\sum\limits_{p\mid T\wedge p\in\text{prime}} \mu (\dfrac{T}{p})$

P4449 于神之怒加强版

$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d=1}^{\min(n,m)}d^k[\gcd(i,j)=d]$

$\sum\limits_{d=1}^{\min(n,m)} d^k\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=d]$

$f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m [\gcd(i,j)=d]$

$g(d)=\sum\limits_{d\mid p} f(p)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor$

$f(n)=\sum\limits_{n\mid d} \mu(\dfrac{d}{n})\times g(d)$

$f(1)=\sum\limits_{d=1}^{\min(n,m)} \mu(d)\times g(d)$

$\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor} [\gcd(i,j)=1]$

$\sum\limits_{i=1}^{\min(n,m)}i^k\sum\limits_{d=1}^{\min(\lfloor\frac{n}{i}\rfloor,\lfloor\frac{m}{i}\rfloor)} \mu(d)\times\lfloor\dfrac{n}{id}\rfloor\times \lfloor\dfrac{m}{id}\rfloor$

$\sum\limits_{T=1}^{\min(n,m)}\lfloor\dfrac{n}{T}\rfloor\times\lfloor\dfrac{m}{T}\rfloor\times \sum\limits_{i\mid T} i^k\times \mu(\dfrac{T}{i})$

迪利克雷卷积有一个牛逼性质，就是卷积之前是积性函数，卷积之后还是积性函数。

所以后面的依托是积性函数，做完了。

[SDOI2014] 数表

形式化的：

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sigma(\gcd(i,j))\times [\sigma(\gcd(i,j))\le a]$

考虑先不管这个 $a$，那么得到：

$\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\frac{m}{d}} \sigma(d)\times[\gcd(i,j)=1]$

提出来：

$\sum\limits_{d=1}^{\min(n,m)}\sigma(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor} \times[\gcd(i,j)=1]$

设：

$f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=x]$

$F(d)=\sum\limits_{d\mid x} f(x)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor$

反演：

$f(x)=\sum\limits_{x\mid d} \mu(\dfrac{d}{x})\times F(d)$

所以：

$f(1)=\sum\limits_{t=1}^{\min(n,m)} \mu(t)\times \lfloor\dfrac{n}{t}\rfloor\times\lfloor\dfrac{m}{t}\rfloor$

所以：

$\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor} \times[\gcd(i,j)=1]=\sum\limits_{t=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)} \mu(t)\times \lfloor\dfrac{n}{dt}\rfloor\times\lfloor\dfrac{m}{dt}\rfloor$

那么枚举 $T=dt$ 得到：

$\sum\limits_{T=1}^{\min(n,m)} \lfloor\dfrac{n}{T}\rfloor\times\lfloor\dfrac{m}{T}\rfloor\times \sum\limits_{d\mid T} \sigma(d)\times \mu(\dfrac{T}{d})$

设：

$g(T)=\sum\limits_{d\mid T} \sigma(d)\times \mu(\dfrac{T}{d})$

那么容易发现只有 $\sigma(d)\le a$ 时才有贡献，所以把所有询问的 $a$ 从小到大排序。

如果随 $a$ 的增加会有 $\sigma(d)$ 对 $g(T)$ 做出贡献，那么就通过枚举倍数的方式添加进去。