MtOI2019 幽灵乐团

我来吃屎了,哈哈啊哈哈哈啊哈哈啊哈!!!!!!!!!

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

lcm(i,j)gcd(i,k)=i×j÷gcd(i,j)gcd(i,k)=i×jgcd(i,k)×gcd(i,j)\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)}

那么考虑把这个式子剥离开,得到:

{P1=i=1Aj=1Bk=1Cif(type)P2=i=1Aj=1Bk=1Cjf(type)P3=i=1Aj=1Bk=1Cgcd(i,j)f(type)P4=i=1Aj=1Bk=1Cgcd(i,k)f(type)ans=P1×P2P3×P4\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=0type=0

先简化 P1,P2P_1,P_2

{P1=(i=1Ai)B×C=(A!)B×CP2=(j=1B)A×C=(B!)A×C\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.

容易想到:

i=1Aj=1Bgcd(i,j)=d=1Adi=1aj=1b[gcd(i,j)=d]\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)=i=1aj=1b[gcd(i,j)=n]f(n)=\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=n]

F(n)=nkf(k)=an×bnF(n)=\sum\limits_{n\mid k}f(k)=\lfloor\dfrac{a}{n}\rfloor\times \lfloor\dfrac{b}{n}\rfloor

对于 F(n)F(n),容易理解如果 gcd(i,j)ngcd(i,j)\mid n,那么 ini\mid njnj\mid n

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

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

f(n)=nkμ(kn)×F(k)f(n)=\sum\limits_{n\mid k}\mu(\lfloor\dfrac{k}{n}\rfloor)\times F(k)

t=kdt=\lfloor\dfrac{k}{d}\rfloor,那么就有:

f(d)=t=1min(ad,bd)μ(t)×atd×btdf(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

也就是:

i=1aj=1b[gcd(i,j)=d]=t=1min(ad,bd)μ(t)×atd×btd\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。

带回原式,得到:

i=1Adt=1min(ad,bd)μ(t)×atd×btd\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=dtT=dt,把 tdtd 一样的放在一起考虑,得到:

Tmin(A,B)(dTdμ(T/d))AT×BT\prod\limits_{T}^{\min(A,B)}(\prod\limits_{d\mid T} d^{\mu(T/d)})^{\frac{A}{T}\times \frac{B}{T}}

枚举 dd,找到 TT 把答案加上去,最后算次方再乘起来,时间复杂度为 O(nlogn)O(n\log n)

type=1type=1

考虑怎么求解:

i=1Aj=1Bk=1Cii×j×k\prod\limits_{i=1}^{A}\prod\limits_{j=1}^B\prod\limits_{k=1}^C i^{i\times j\times k}

把后面提出来,得到:

i=1Aij×(j1)×k×(k1)4\prod\limits_{i=1}^A i^{\dfrac{j\times (j-1)\times k\times (k-1)}{4}}

需要用欧拉降幂。

考虑后面怎么推:

i=1Aj=1Bk=1Cgcd(i,j)i×j×k\prod\limits_{i=1}^{A}\prod\limits_{j=1}^B\prod\limits_{k=1}^C \gcd(i,j)^{i\times j\times k}

k=1C\prod\limits_{k=1}^C 拿出来,得到:

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

类似于 type=0type=0 的时候,我们可以发反演得到:

T=1min(A,B)(dTdμ(T/d))T2×S(A/T)×S(B/T)\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)=x×(x1)2S(x)=\dfrac{x\times(x-1)}{2}

type=2type=2

对于指数的情况,直接开 log\log

得到:

i=1Aj=1Bk=1Cgcd(i,j,k)×ln(lcm(i,j)gcd(i,k))\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=dnφ(d)n=\sum\limits_{d\mid n}\varphi(d)

那么:

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

带入,得到:

i=1Aj=1Bk=1Cdgcd(i,j,k)φ(d)×ln(lcm(i,j)gcd(i,k))\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)})

idi,jdj,kdki\gets di,j\gets dj,k\gets dk,得到:

d=1min(A,B,C)i=1Adj=1Bdk=1Cdφ(d)×ln(lcm(id,jd)gcd(id,kd)\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)}

φ(d)\varphi(d) 拿出来,得到:

d=1min(A,B,C)φ(d)i=1Adj=1Bdk=1Cdln(lcm(id,jd)gcd(id,kd)\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)}

把后面的 dd 消了:

d=1min(A,B,C)φ(d)i=1Adj=1Bdk=1Cdln(lcm(i,j)gcd(i,k)\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\ln 拿掉得到:

d=1min(A,B,C)(i=1Adj=1Bdk=1Cdlcm(i,j)gcd(i,k))φ(d)\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=0type=0 的情况,做完了。

实现

一些数组的意义:

f1(n)=T=1niTiμ(Ti)f_1(n)=\prod\limits_{T=1}^n\prod\limits_{i\mid T}i^{\mu (\frac{T}{i})}

f2(n)=T=1n(iTiμ(Ti))T2f_2(n)=\prod\limits_{T=1}^n(\prod\limits_{i\mid T}i^{\mu(\frac{T}{i})})^{T^2}

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

F(A,B)=T=1min(A,B)(dTdμ(T/d))S(A/T)×S(B/T)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)=T=1min(A,B)(dTdμ(T/d))T2×S(A/T)×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)=xiyj[gcd(x,y)=1]d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j}[\gcd(x,y)=1]

所以原式求解的就是:

i=1nj=1mxiyj[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,ji,j 对答案并没有实际的影响,把 x,yx,y 替换为 i,ji,j

i=1nj=1mni×mj×[gcd(i,j)=1]\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)=i=1nj=1mni×mj×[gcd(i,j)=x]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)=xnf(n)=i=1nij=1mjnix×mjxg(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)=pxμ(xp)g(x)=pxμ(xp)i=1nij=1mjnix×mjxf(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)=t=1min(n,m)μ(t)i=1ntj=1mjnit×mjtf(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的数字表格

套路的转化 lcm\text{lcm},得到:

i=1nj=1mi×jgcd(i,j)\sum\limits_{i=1}^n\sum\limits_{j=1}^m\dfrac{i\times j}{\gcd(i,j)}

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

d=1min(n,m)d×i=1ndj=1md[gcd(i,j)=1]×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)=i=1nj=1m[gcd(i,j)=d]×i×jf(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[\gcd(i,j)=d]\times i\times j

g(d)=dnf(n)=nd×md×g(d)=\sum\limits_{d\mid n} f(n)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor\times

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

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

那么得到:

d=1min(n,m)di=1ndj=1mdxgcd(i,j)μ(x)×ij\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

简化得到:

d=1min(n,m)dx=1min(nd,md)μ(x)i=1ndj=1mdij×[xgcd(i,j)]\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)]

那么继续 iix,jjxi\gets ix,j\gets jx,得到:

d=1min(n,m)dx=1min(nd,md)μ(x)i=1ndxj=1mdxij×x2\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

拿出来得到:

d=1min(n,m)dx=1min(nd,md)μ(x)×x2(i=1ndxi)×(j=1mdxj)\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)=x×(x+1)2S(x)=\dfrac{x\times(x+1)}{2},则:

d=1min(n,m)dx=1min(nd,md)μ(x)×x2×S(ndx)×S(mdx)\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=dxT=dx,则:

Tmin(n,m)S(nT)×S(mT)T=dxd×x2×μ(x)\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)

那么就得到了:

Tmin(n,m)S(nT)×S(mT)×T×xTμ(x)×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×xTμ(x)×xf(T)=T\times \sum\limits_{x\mid T}\mu(x)\times x

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

P2257 YY的GCD

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

pp 拿出来:

pprimei=1npj=1mp[gcd(i,j)=1]\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)=i=1Nj=1M[gcd(i,j)=n]f(n)=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[\gcd(i,j)=n]

g(d)=dnf(n)=Nd×Mdg(d)=\sum\limits_{d\mid n} f(n)=\lfloor\dfrac{N}{d}\rfloor\times \lfloor\dfrac{M}{d}\rfloor

得到:

f(n)=ndμ(dn)×g(d)=ndμ(dn)×Nd×Mdf(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)=d=1min(N,M)μ(d)×Nd×Mdf(1)=\sum\limits_{d=1}^{\min(N,M)}\mu(d)\times \lfloor\dfrac{N}{d}\rfloor\times \lfloor\dfrac{M}{d}\rfloor

因为 N=npN=\lfloor\frac{n}{p}\rfloorM=mpM=\lfloor\frac{m}{p}\rfloor,所以带入得到:

pprimed=1min(np,mp)μ(d)×npd×mpd\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=pdT=pd,那么:

pprimeT=1,pTmin(n,m)μ(Tp)×nT×mT\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

那么改变一下顺序:

T=1min(n,m)nT×mTpTpprimeμ(Tp)\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 于神之怒加强版

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

d=1min(n,m)dki=1nj=1m[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)=i=1nj=1m[gcd(i,j)=d]f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m [\gcd(i,j)=d]

g(d)=dpf(p)=nd×mdg(d)=\sum\limits_{d\mid p} f(p)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor

f(n)=ndμ(dn)×g(d)f(n)=\sum\limits_{n\mid d} \mu(\dfrac{d}{n})\times g(d)

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

d=1min(n,m)dki=1ndj=1md[gcd(i,j)=1]\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]

i=1min(n,m)ikd=1min(ni,mi)μ(d)×nid×mid\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

T=1min(n,m)nT×mT×iTik×μ(Ti)\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] 数表

形式化的:

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

考虑先不管这个 aa,那么得到:

d=1min(n,m)i=1ndj=1mdσ(d)×[gcd(i,j)=1]\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]

提出来:

d=1min(n,m)σ(d)i=1ndj=1md×[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)=i=1nj=1m[gcd(i,j)=x]f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=x]

F(d)=dxf(x)=nd×mdF(d)=\sum\limits_{d\mid x} f(x)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor

反演:

f(x)=xdμ(dx)×F(d)f(x)=\sum\limits_{x\mid d} \mu(\dfrac{d}{x})\times F(d)

所以:

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

所以:

i=1ndj=1md×[gcd(i,j)=1]=t=1min(nd,md)μ(t)×ndt×mdt\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=dtT=dt 得到:

T=1min(n,m)nT×mT×dTσ(d)×μ(Td)\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)=dTσ(d)×μ(Td)g(T)=\sum\limits_{d\mid T} \sigma(d)\times \mu(\dfrac{T}{d})

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

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