夏晓光(loveJY)的博客

转载自洛谷博客

orzhq真的强大啊

模板题，没啥好说的

$b_k=\sum_{i|k}a_i$

然后给出$a_i$求$b_i$

做法就是考虑一个数是另一个数的约数当且仅当满足所有质因子的指数都小于等于另一个数。

然后你会发现这个就是高维前缀和啊

然后就可以质因数分解后指数的高维前缀和

for(int i = 1;i <= tot;i ++)
	for(int j = 1;pri[i] * j <= n;j ++)
		a[pri[i] * j] += a[j];

然后最后还有一个后缀和，就是考虑把这个循环改改，+变成-

$b_k=\sum_{k|i}c_i$

for(int i=tot;i>=1;--i)
	for(int j=1;pri[i]*j<=n;++j)
    	a[j]-=a[pri[i]*j]

没有了