出题人题解。

说实话我是真没想到会有人打表做这一题。

暴力

按照题意模拟或直接输出 $g_1$ 可获得 $4\text{pts}$。

实现较优的暴力可以获得 $12\text{pts}$ 或以上。

特殊性质 A

所有的 $g_i$ 均相同，此时答案与具体位置无关，只与所有位置被计算次数总和有关。

考虑所有的 range(a,b,c) 总共包含多少个位置，答案形如若干个等差数列求和。

特殊性质 B

由于只有 $g_n\neq 0$， 考虑计算有多少个 range(a,b,c) 包含 $n$。

首先必须满足 $b=n+1$。此时我们只关注 range(a,b,c) 中的 $a,c$。具体来说，令 $x=n-a$，若 $c|n-a$，则 $n$ 在 range(a,b,c) 中，注意当 $x=0$ 时要特殊处理。

设 $d_x$ 表示 $x$ 的因子个数，则答案为 $g_{n}(n+\sum\limits_{i=1}^{n-1} d_{i})$。

正解

特殊性质 B 启发我们对每一个位置计算其被计算的次数。

但与特殊性质 B 有一点不同的是， range(a,b,c) 中的 $b$ 并不一定要是 $n+1$。

设 $f_x=n+\sum\limits_{i=1}^{x-1} d_{i}$，则答案为 $\sum\limits_{i=1}^{n} (n-i+1)g_i f_i$。

根据实现方法不同，可获得 $24\text{pts}\sim 100\text{pts}$，以下是一些不同的实现方法：

暴力求因子个数，时间复杂度 $O(n^2)$，可以获得 $24\text{pts}$。

对于每个数直接计算因子个数，时间复杂度 $O(n\sqrt n)$，可以获得 $36\text{pts}\sim 48\text{pts}$。

枚举倍数计算因子个数，时间复杂度 $O(n\ln n)$，可以获得 $76\text{pts}\sim 84\text{pts}$。

注意到一个数的因子个数函数是积性函数，因此可以使用欧拉筛求出因子个数，时间复杂度 $O(n)$，可以获得 $100\text{pts}$。