Description

Solution

很明顯可以發現，n和m交換是不會影響答案的， 我們可以先設一個f(x)=∑d|xd$f(x)=/sum_{d|x}d$表示i$i$的約數和，還有一個數組g(x)=∑ni=1∑mj=1(gcd(i,j)=x)$g(x)=/sum_{i=1}^{n}/sum_{j=1}^{m}(gcd(i,j)=x)$，而答案明顯就是∑ni=1f(i)?g(i)$/sum_{i=1}^{n}f(i)*g(i)$，看到了g(x)$g(x)$中的gcd$gcd$可以很快能夠想到莫比烏斯反演，對g(x)$g(x)$我們化簡一下： g(x)=∑?ni?i=1∑?mj?j=1∑d=gcd(i,j)μ(d)$g(x)=/sum_{i=1}^{/lfloor{n/over i}/rfloor}/sum_{j=1}^{/lfloor{m/over j}/rfloor}/sum_{d=gcd(i,j)}μ(d)$ =∑x|dμ(d)?nd??md?$=/sum_{x|d}μ(d){/lfloor{n/over d}/rfloor}{/lfloor{m/over d}/rfloor}$ 然后把化簡后的g(x)$g(x)$代入求答案得： ans=∑ni=1f(i)∑x|dμ(d)?nd??md?$ans=/sum_{i=1}^{n}f(i)/sum_{x|d}μ(d){/lfloor{n/over d}/rfloor}{/lfloor{m/over d}/rfloor}$ =∑nd=1?nd??md?∑i|df(i)?μ(di)$=/sum_{d=1}^{n}{/lfloor{n/over d}/rfloor}{/lfloor{m/over d}/rfloor}/sum_{i|d}f(i)*μ({d/over i})$ 我們令h(i)=∑i|df(i)?μ(di)$h(i)=/sum_{i|d}f(i)*μ({d/over i})$，因為只有當f(x)≤a$f(x)≤a$的時候才有貢獻，所以，把所有詢問按照a$a$從小到大離線排序，然后把符合條件的f(x)$f(x)$一個個加入進去，而對于h(i)$h(i)$我們可以用前綴和來維護。

Code