在今天月赛 Div2 T2 考场上我写了如下代码:

int n, a[N];
uint f[N][N], g[N][N], ans;
int main() {
    n = read(); For(i, 1, n) a[i] = read();
    sort(a + 1, a + n + 1), reverse(a + 1, a + n + 1);
    For(i, 1, n) For(j, i, n) f[i][j] = f[i][j - 1] + a[i] / a[j];
    For(j, 1, n) {
        for (int l = j + 1, r = 0; l <= n; l = r + 1) {
            r = l; int val = a[j] / a[l];
            while (r < n && a[j] / a[r + 1] == val) ++r;
            For(i, 1, j - 1) g[i][j] += (f[i][r] - f[i][l - 1]) * val;
        }
    }
    For(i, 1, n) For(j, i + 1, n) 
        ans += a[i] / a[j] * g[i][j];
    put(ans);
	return 0;
}

本机 1~n 的数据跑了 9s 左右，洛谷 2.5s 跑过。

为了使数组访问连续，我将其 f，g 两个数组两位交换，改成这样:

int n, a[N], cnt;
uint f[N][N], g[N][N], ans;
int main() {
    n = read(); For(i, 1, n) a[i] = read();
    sort(a + 1, a + n + 1), reverse(a + 1, a + n + 1);
    For(i, 1, n) For(j, i, n) f[j][i] = f[j - 1][i] + a[i] / a[j];
    For(j, 1, n) {
        for (int l = j + 1, r = 0; l <= n; l = r + 1) {
            r = l; int val = a[j] / a[l];
            while (r < n && a[j] - val * a[r + 1] < a[r + 1]) ++r;
            For(i, 1, j - 1) g[j][i] += (f[r][i] - f[l - 1][i]) * val, ++cnt;
        }
    }
    For(j, 1, n) For(i, 1, j - 1)
        ans += a[i] / a[j] * g[j][i];
    put(ans);
	return 0;
}

本机只跑了 0.6s，洛谷 0.7s。

经测试，1~n 的数据有 1e9 的枚举量，不能理解。。。