入门反演套路

· · 个人记录

入门的反演题一般都长这样(设n\leq m):

\sum\limits_{i=1}^n\sum\limits_{j=1}^mf(i)g(j)h(\gcd(i,j))

于是开始套路(约定除法均为下取整)

原式=\sum\limits_{d=1}^nh(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^mf(i)g(j)[\gcd(i,j)==d] (枚举d=\gcd(i,j))

=\sum\limits_{d=1}^nh(d)\sum\limits_{id=1}^n\sum\limits_{jd=1}^mf(id)g(jd)[\gcd(id,jd)==d] =\sum\limits_{d=1}^nh(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}f(id)g(jd)[\gcd(i,j)==1] =\sum\limits_{d=1}^nh(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}f(id)g(jd)\sum\limits_k\mu(k)[k|\gcd(i,j)]\qquad$(因为$[n=1]=\sum\limits_{d|n}\mu(d)) $=\sum\limits_{d=1}^nh(d)\sum\limits_{k=1}^{\frac{n}{d}}\mu(k)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}f(id)g(jd)[k|i][k|j]\qquad$(交换求和号的问题下面再说) $=\sum\limits_{d=1}^nh(d)\sum\limits_{k=1}^{\frac{n}{d}}\mu(k)\sum\limits_{ik=1}^{\frac{n}{d}}\sum\limits_{jk=1}^{\frac{m}{d}}f(ikd)g(jkd)[k|ik][k|jk]\qquad$($k|ik$好像十分显然) $=\sum\limits_{d=1}^nh(d)\sum\limits_{k=1}^{\frac{n}{d}}\mu(k)\sum\limits_{i=1}^{\frac{n}{kd}}\sum\limits_{j=1}^{\frac{m}{kd}}f(ikd)g(jkd)

设T=kd,F(n,m)=\sum\limits_{i=1}^{n}f(im),G(n,m)=\sum\limits_{i=1}^{n}g(im)则原式

=\sum\limits_{T=1}^nF(\frac{n}{T},T)G(\frac{m}{T},T)\sum\limits_{d|T}h(d)\mu(\frac{T}{d})\qquad$(把$T$拉到外面，然后有$d|T$和$k=\frac{T}{d}

于是只要F和G都可以快速计算就好了，预处理h\ast\mu然后数论分块.预处理的方法是枚举约数.

使用rqy的做法可以更快地得到这个式子

关于交换求和号，我们注意到所有的约束条件都可以用[P]的形式写到最后面去，而几个求和指标的任意交换是没有问题的.

进阶反演题一方面是增大F与G的处理难度，另一方面是把二元求和换成多元的...