MtOI2019 幽灵乐团
我来吃屎了,哈哈啊哈哈哈啊哈哈啊哈!!!!!!!!!
发现对于题目要求的式子:
gcd(i,k)lcm(i,j)=gcd(i,k)i×j÷gcd(i,j)=gcd(i,k)×gcd(i,j)i×j
那么考虑把这个式子剥离开,得到:
⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧P1=i=1∏Aj=1∏Bk=1∏Cif(type)P2=i=1∏Aj=1∏Bk=1∏Cjf(type)P3=i=1∏Aj=1∏Bk=1∏Cgcd(i,j)f(type)P4=i=1∏Aj=1∏Bk=1∏Cgcd(i,k)f(type)ans=P3×P4P1×P2
type=0
先简化 P1,P2:
⎩⎪⎪⎨⎪⎪⎧P1=(i=1∏Ai)B×C=(A!)B×CP2=(j=1∏B)A×C=(B!)A×C
容易想到:
i=1∏Aj=1∏Bgcd(i,j)=d=1∏Ad∑i=1a∑j=1b[gcd(i,j)=d]
考虑怎么把指数上的式子反演掉,设:
f(n)=i=1∑aj=1∑b[gcd(i,j)=n]
F(n)=n∣k∑f(k)=⌊na⌋×⌊nb⌋
对于 F(n),容易理解如果 gcd(i,j)∣n,那么 i∣n,j∣n。
因为 [1,a] 中有 ⌊na⌋ 个,[1,b] 中有 ⌊nb⌋ 个且两两组合都可以,所以 F(n)=⌊na⌋×⌊nb⌋。
那么对这个式子进行莫比乌斯反演,得到:
f(n)=n∣k∑μ(⌊nk⌋)×F(k)
设 t=⌊dk⌋,那么就有:
f(d)=t=1∑min(⌊da⌋,⌊db⌋)μ(t)×⌊tda⌋×⌊tdb⌋
也就是:
i=1∑aj=1∑b[gcd(i,j)=d]=t=1∑min(⌊da⌋,⌊db⌋)μ(t)×⌊tda⌋×⌊tdb⌋
发现就是「HAOI2011」Problem b。
带回原式,得到:
i=1∏Adt=1∑min(⌊da⌋,⌊db⌋)μ(t)×⌊tda⌋×⌊tdb⌋
设 T=dt,把 td 一样的放在一起考虑,得到:
T∏min(A,B)(d∣T∏dμ(T/d))TA×TB
枚举 d,找到 T 把答案加上去,最后算次方再乘起来,时间复杂度为 O(nlogn)。
type=1
考虑怎么求解:
i=1∏Aj=1∏Bk=1∏Cii×j×k
把后面提出来,得到:
i=1∏Ai4j×(j−1)×k×(k−1)
需要用欧拉降幂。
考虑后面怎么推:
i=1∏Aj=1∏Bk=1∏Cgcd(i,j)i×j×k
把 k=1∏C 拿出来,得到:
(i=1∏Aj=1∏Bgcd(i,j)i×j)2k×(k+1)
类似于 type=0 的时候,我们可以发反演得到:
T=1∏min(A,B)(d∣T∏dμ(T/d))T2×S(A/T)×S(B/T)
其中 S(x)=2x×(x−1)。
type=2
对于指数的情况,直接开 log。
得到:
i=1∑Aj=1∑Bk=1∑Cgcd(i,j,k)×ln(gcd(i,k)lcm(i,j))
考虑证明一下,有欧拉反演:
n=d∣n∑φ(d)
那么:
gcd(i,j,k)=d∣gcd(i,j,k)∑φ(d)
带入,得到:
i=1∑Aj=1∑Bk=1∑Cd∣gcd(i,j,k)∑φ(d)×ln(gcd(i,k)lcm(i,j))
令 i←di,j←dj,k←dk,得到:
d=1∑min(A,B,C)i=1∑dAj=1∑dBk=1∑dCφ(d)×ln(gcd(id,kd)lcm(id,jd)
把 φ(d) 拿出来,得到:
d=1∑min(A,B,C)φ(d)i=1∑dAj=1∑dBk=1∑dCln(gcd(id,kd)lcm(id,jd)
把后面的 d 消了:
d=1∑min(A,B,C)φ(d)i=1∑dAj=1∑dBk=1∑dCln(gcd(i,k)lcm(i,j)
那么整体把 ln 拿掉得到:
d=1∏min(A,B,C)(i=1∏dAj=1∏dBk=1∏dCgcd(i,k)lcm(i,j))φ(d)
发现里面就是 type=0 的情况,做完了。
实现
一些数组的意义:
f1(n)=T=1∏ni∣T∏iμ(iT)
f2(n)=T=1∏n(i∣T∏iμ(iT))T2
phi(n)=i=1∑nφ(i)
F(A,B)=T=1∏min(A,B)(d∣T∏dμ(T/d))S(A/T)×S(B/T)
G(A,B)=T=1∏min(A,B)(d∣T∏dμ(T/d))T2×S(A/T)×S(B/T)
SDOI2015 约数个数和
感性理解,发现:
d(ij)=x∣i∑y∣j∑[gcd(x,y)=1]
所以原式求解的就是:
i=1∑nj=1∑mx∣i∑y∣j∑[gcd(x,y)=1]
显然 i,j 对答案并没有实际的影响,把 x,y 替换为 i,j。
i=1∑nj=1∑m⌊in⌋×⌊jm⌋×[gcd(i,j)=1]
套路的,设:
f(x)=i=1∑nj=1∑m⌊in⌋×⌊jm⌋×[gcd(i,j)=x]
g(x)=x∣n∑f(n)=i=1∑inj=1∑jm⌊ixn⌋×⌊jxm⌋
所以反演得到:
f(p)=p∣x∑μ(px)g(x)=p∣x∑μ(px)i=1∑inj=1∑jm⌊ixn⌋×⌊jxm⌋
所以:
f(1)=t=1∑min(n,m)μ(t)i=1∑tnj=1∑jm⌊itn⌋×⌊jtm⌋
P1829 Crash的数字表格
套路的转化 lcm,得到:
i=1∑nj=1∑mgcd(i,j)i×j
那么枚举 gcd(i,j) 的值:
d=1∑min(n,m)d×i=1∑⌊dn⌋j=1∑⌊dm⌋[gcd(i,j)=1]×i×j
不经典的反演:
f(d)=i=1∑nj=1∑m[gcd(i,j)=d]×i×j
g(d)=d∣n∑f(n)=⌊dn⌋×⌊dm⌋×
byd,反演不出来,还需要继续简化,有一个暴强的性质:
d∣n∑μ(d)=[n=1]
那么得到:
d=1∑min(n,m)di=1∑⌊dn⌋j=1∑dmx∣gcd(i,j)∑μ(x)×ij
简化得到:
d=1∑min(n,m)dx=1∑min(⌊dn⌋,⌊dm⌋)μ(x)i=1∑⌊dn⌋j=1∑⌊dm⌋ij×[x∣gcd(i,j)]
那么继续 i←ix,j←jx,得到:
d=1∑min(n,m)dx=1∑min(⌊dn⌋,⌊dm⌋)μ(x)i=1∑⌊dxn⌋j=1∑⌊dxm⌋ij×x2
拿出来得到:
d=1∑min(n,m)dx=1∑min(⌊dn⌋,⌊dm⌋)μ(x)×x2(i=1∑⌊dxn⌋i)×(j=1∑⌊dxm⌋j)
那么设 S(x)=2x×(x+1),则:
d=1∑min(n,m)dx=1∑min(⌊dn⌋,⌊dm⌋)μ(x)×x2×S(⌊dxn⌋)×S(⌊dxm⌋)
那么设 T=dx,则:
T∑min(n,m)S(⌊Tn⌋)×S(⌊Tm⌋)T=dx∑d×x2×μ(x)
那么就得到了:
T∑min(n,m)S(⌊Tn⌋)×S(⌊Tm⌋)×T×x∣T∑μ(x)×x
关于实现:
f(T)=T×x∣T∑μ(x)×x
预处理 f(T),其他分块即可。
P2257 YY的GCD
p∈prime∑i=1∑nj=1∑m[gcd(i,j)=p]
把 p 拿出来:
p∈prime∑i=1∑⌊pn⌋j=1∑⌊pm⌋[gcd(i,j)=1]
反演:
f(n)=i=1∑Nj=1∑M[gcd(i,j)=n]
g(d)=d∣n∑f(n)=⌊dN⌋×⌊dM⌋
得到:
f(n)=n∣d∑μ(nd)×g(d)=n∣d∑μ(nd)×⌊dN⌋×⌊dM⌋
所以:
f(1)=d=1∑min(N,M)μ(d)×⌊dN⌋×⌊dM⌋
因为 N=⌊pn⌋,M=⌊pm⌋,所以带入得到:
p∈prime∑d=1∑min(⌊pn⌋,⌊pm⌋)μ(d)×⌊pdn⌋×⌊pdm⌋
设 T=pd,那么:
p∈prime∑T=1,p∣T∑min(n,m)μ(pT)×⌊Tn⌋×⌊Tm⌋
那么改变一下顺序:
T=1∑min(n,m)⌊Tn⌋×⌊Tm⌋p∣T∧p∈prime∑μ(pT)
P4449 于神之怒加强版
i=1∑nj=1∑md=1∑min(n,m)dk[gcd(i,j)=d]
d=1∑min(n,m)dki=1∑nj=1∑m[gcd(i,j)=d]
f(d)=i=1∑nj=1∑m[gcd(i,j)=d]
g(d)=d∣p∑f(p)=⌊dn⌋×⌊dm⌋
f(n)=n∣d∑μ(nd)×g(d)
f(1)=d=1∑min(n,m)μ(d)×g(d)
d=1∑min(n,m)dki=1∑⌊dn⌋j=1∑⌊dm⌋[gcd(i,j)=1]
i=1∑min(n,m)ikd=1∑min(⌊in⌋,⌊im⌋)μ(d)×⌊idn⌋×⌊idm⌋
T=1∑min(n,m)⌊Tn⌋×⌊Tm⌋×i∣T∑ik×μ(iT)
迪利克雷卷积有一个牛逼性质,就是卷积之前是积性函数,卷积之后还是积性函数。
所以后面的依托是积性函数,做完了。
[SDOI2014] 数表
形式化的:
i=1∑nj=1∑mσ(gcd(i,j))×[σ(gcd(i,j))≤a]
考虑先不管这个 a,那么得到:
d=1∑min(n,m)i=1∑⌊dn⌋j=1∑dmσ(d)×[gcd(i,j)=1]
提出来:
d=1∑min(n,m)σ(d)i=1∑⌊dn⌋j=1∑⌊dm⌋×[gcd(i,j)=1]
设:
f(x)=i=1∑nj=1∑m[gcd(i,j)=x]
F(d)=d∣x∑f(x)=⌊dn⌋×⌊dm⌋
反演:
f(x)=x∣d∑μ(xd)×F(d)
所以:
f(1)=t=1∑min(n,m)μ(t)×⌊tn⌋×⌊tm⌋
所以:
i=1∑⌊dn⌋j=1∑⌊dm⌋×[gcd(i,j)=1]=t=1∑min(⌊dn⌋,⌊dm⌋)μ(t)×⌊dtn⌋×⌊dtm⌋
那么枚举 T=dt 得到:
T=1∑min(n,m)⌊Tn⌋×⌊Tm⌋×d∣T∑σ(d)×μ(dT)
设:
g(T)=d∣T∑σ(d)×μ(dT)
那么容易发现只有 σ(d)≤a 时才有贡献,所以把所有询问的 a 从小到大排序。
如果随 a 的增加会有 σ(d) 对 g(T) 做出贡献,那么就通过枚举倍数的方式添加进去。