$$
s _ k = \sum _ {i | k} a _i
$$
求每一个 $s _ i$ 。
复杂度 $O(n \log \log n)$ 。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <cstdio>
using namespace std;
const int N = 2e7 + 10;
bool vis[N];
int n, s[N], cnt, p[N];
void init()
{
vis[1] = true;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
p[++cnt] = i;
for (int j = 1; j <= cnt && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
break;
}
}
}
int main()
{
scanf("%d", &n);
init();
for (int i = 1; i <= n; i++)
scanf("%d", &s[i]);
for (int i = 1; i <= cnt; i++)
for (int j = 1; p[i] * j <= n; j++)
s[p[i] * j] += s[j];
for (int i = 1; i <= n; i++)
printf("%d ", s[i]);
return 0;
}
|
如果是后缀和
查看代码
1
2
3
| for (int i = 1; i <= cnt; ++i)
for (int j = n / p[i]; j; --j)
s[j] += s[p[i] * j];
|
一个 trick ，求对于 $i \in [1, n]$ 求 $\gcd(i, n)$ ，可以在 $O(n \log \log n)$ 的时间内完成。$O(\sqrt n)$ 枚举 $n$ 的约数，标记 $f _ i = i$ ，否则 $f _ i = 1$ ，做狄利克雷前缀最大值即可。