[hdu6868] absolute math (pusher + Mobius inversion)

Topic link

The question ：

Make $f(n)={\sum }_{d|n}|\mu (d)|$.$T$ Group inquiry , Each group is given one $n$ and $m$, seek ${\sum }_{i=1}^{m}f(ni)$.
$(1\le T\le 10^4,1\le n,m\le 10^7)$

deduction ：

First, according to the Mobius function $\mu (n)$ The definition of can be known , When $n$ When there is a square factor ,$|\mu (n)|=0$, otherwise $|\mu (n)|=1$.

therefore $f(n)$ It means $n$ Of the factors , Number of factors without square factor .

We will $n$ Find out all the qualitative factors , Because there can't be a square factor , So the number of times of each prime factor is either $0$, Either for $1$. Got it. $f(n)=2^{w(n)}$, among $w(n)$ Express $n$ How many different qualitative factors .

According to the above formula , You can find $f(ab)=\frac{f(a)f(b)}{f(gcd(a,b))}=2^{w(a)+w(b)-w(gcd(a,b))}$.

It's out $gcd$ after , We consider Mobius inversion , We need to put $gcd$ Bring up , The original formula becomes .
$$\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)]$$

Now start Mobius inversion , Make $y(g)={\sum }_{i=1}^m{2}^{w(n)+w(i)}[g=gcd(n,i)]$.

Then make $Y(d)={\sum }_{d|g}y(g)$, namely ,
$$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)}$$

Then there are $y(g)={\sum }_{g|d}\mu (d/g)Y(d)$.

The original formula becomes ,
$$\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)$$
We make $G(d)={\sum }_{g|d}{2}^{-w(g)}\mu (d/g)$, Sure $o(nlogn)$ Preprocess this function , Then turn the formula .
$$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)}$$

Code :

 Insert a code chip here