[hdu6868]Absolute Math（推式子+莫比乌斯反演）

题目链接

题意：

令$f(n)={\sum }_{d|n}|\mu (d)|$。$T$组询问，每组给定一个$n$和$m$，求${\sum }_{i=1}^{m}f(ni)$。
$(1\le T\le 10^4,1\le n,m\le 10^7)$

推导：

首先根据莫比乌斯函数$\mu (n)$的定义式可以知道，当$n$存在平方因子时，$|\mu (n)|=0$，否则$|\mu (n)|=1$。

所以$f(n)$表示的是$n$的因子中，不存在平方因子的因子个数。

我们将$n$的质因子全部找出来，因为不能有平方因子，所以每个质因子的次数要么为$0$，要么为$1$。就得到了$f(n)=2^{w(n)}$，其中$w(n)$表示$n$有多少个不同的质因子。

根据上面推出来的式子，可以发现$f(ab)=\frac{f(a)f(b)}{f(gcd(a,b))}=2^{w(a)+w(b)-w(gcd(a,b))}$。

弄出了$gcd$之后，我们考虑莫比乌斯反演，就要先把$gcd$提出来，原式就变成。
$$\sum _{i=1}^{m}f(ni)=\sum _{g=1}^{min(n,m)}{2}^{-w(g)}\sum _{i=1}^m{2}^{w(n)+w(i)}[g=gcd(n,i)]$$

现在开始莫比乌斯反演，令$y(g)={\sum }_{i=1}^m{2}^{w(n)+w(i)}[g=gcd(n,i)]$。

然后令$Y(d)={\sum }_{d|g}y(g)$，即，
$$Y(d)=\sum _{d|g}\sum _{i=1}^m{2}^{w(n)+w(i)}[g=gcd(n,i)]=\sum _{i=1}^m\sum _{d|n}\sum _{d|i}{2}^{w(n)+w(i)}$$

则有$y(g)={\sum }_{g|d}\mu (d/g)Y(d)$。

原式就变成了，
$$\sum _{g=1}^{min(n,m)}y(g)=\sum _{g=1}^{min(n,m)}{2}^{-w(g)}\sum _{g|d}\mu (d/g)\sum _{d|n}\sum _{i=1}^m\sum _{d|i}{2}^{w(n)+w(i)}=2^{w(n)}\sum _{i=1}^m{2}^{w(i)}\sum _{d|n}\sum _{d|i}\sum _{g|d}{2}^{-w(g)}\mu (d/g)$$
我们令$G(d)={\sum }_{g|d}{2}^{-w(g)}\mu (d/g)$，可以$o(nlogn)$预处理这个函数，然后接着化式子。
$$ANS=2^{w(n)}\sum _{i=1}^m{2}^{w(i)}\sum _{d|n}\sum _{d|i}G(d)=2^{w(n)}\sum _{d|n}G(d)\sum _{i=1}^m\sum _{d|i}{2}^{w(i)}=2^{w(n)}\sum _{d|n}G(d)\sum _{i=1}^{\lfloor \frac{m}{d}\rfloor }{2}^{w(id)}$$

代码:

在这里插入代码片