P5495 Dirichlet 前缀和

(1 min to read)

$b_k = \sum_{i \mid k} a_i$求数组b考虑下标i和j,对其质因数分解,当且仅当i的所有质因数的幂次<=j的,i才是j的因数,可以有贡献发现这个实际上就是一个关于质因子分解后的指数的高维前缀和,使用类似FMT的方法就可以了复杂度$O(n\log \log n)$

1
2
3
for(int i=1; i<=prime[0]; i++)
for(int j=1; 1ll*j*prime[i]<=n; j++)
b[j*prime[i]] += b[j];