题解 P5495 【【模板】Dirichlet 前缀和】

watermoon · 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];