自动搬运

查看原文

来自洛谷，原作者为

	watermoon 你永远是我最好的朋友。

搬运于2025-08-24 22:11:21，当前版本为作者最后更新于2019-08-09 22:23:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设$i=\prod p_k^{\alpha_k},j=\prod p_k^{\beta_k}$，那么$a_i$贡献到$b_j$当且仅当$\forall k,\alpha_k\leq \beta_k$.

发现这个实际上就是一个关于质因子分解后的指数的高维前缀和，使用类似FMT的方法就可以了。

根据埃氏筛的时间复杂度分析，$T(n)=\sum\limits_p\lfloor\frac{n}{p}\rfloor=O(n\log\log n)$。

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