洛谷P9148 除法题题解

题意：

给定大小为 $n$ 的集合 $a$，保证其中元素互不相同且均为正整数。

如果我们从中按顺序取出三个元素 $a, b, c$，则共有 $n \cdot (n-1) \cdot (n-2)$ 种不同的选择方案。

现在对于一种选择方案 $(a,b,c)$，定义其权值为 $\Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor\Bigl\lfloor\dfrac{a}{c}\Bigr\rfloor\Bigl\lfloor\dfrac{b}{c}\Bigr\rfloor$。

你需要对所有的选择方案计算权值的总和，你只需输出这个总和对 $2^{32}$ 取模的结果。

注：$\lfloor a\rfloor$ 表示不大于 $a$ 的最大整数。如 $\lfloor 2.4\rfloor=2$、$\lfloor 5\rfloor=5$。

输入格式：

第一行，一个正整数 $n$，表示序列的长度。

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$，每个数描述了集合 $a$ 的一个元素，这些数互不相同。

输出格式：

输出一行一个整数，表示答案对 $2^{32}$ 取模的结果。

数据范围：

对于 $100\%$ 的数据，$1 \le n, a_i \le 5000$。

很容易想到去枚举 $a,b$ ，但是仔细想想会发现 $c$ 很不好枚举

相反，如果我们枚举 $c$ ，考察它对哪些 $a,b$ 产生了贡献，这却是能做的。

可以发现，因为值域 $V$ 很小，所以 $\left\lfloor \frac{V}{c}\right\rfloor$ 的值域则更为小。

并且对于一个 $\left\lfloor \frac{a}{c}\right\rfloor$ ，它包含了 $[a_1, a_2]$ 内的所有整数，所有 $a \in [a_1,a_2]$ 的 $\left\lfloor \frac{a}{c}\right\rfloor$ 是相等的

那么对于 $\left\lfloor \frac{a}{c}\right\rfloor,\left\lfloor \frac{b}{c}\right\rfloor$ ，它包含了一个矩阵 $(a_1,b_1),(a_2,b_2)$ 内的所有点，这个统计很容易由二维差分做到。

分析一下时间复杂度。枚举 $c$ 这一部分的时间复杂度为

$\sum_{i=1}^V \frac{V}{i} \times \frac{V}{i}=V^2 \times \sum_{i=1}^V \frac{1}{i^2}$

这里需要一个小知识

$\sum_{i = 1}^{\infty} \frac{1}{i^2}=\frac{\pi^2}{6}$

因此这部分的时间复杂度为 $\mathcal{O}(V^2)$ 。枚举 $a,b$ 计算答案的部分显然也是 $\mathcal{O}(V^2)$

总时间复杂度 $\mathcal{O}(V^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))

const int m = 5000;
char vis[N]; int a[N],b[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], vis[a[i]] = true;
    for(int c = 1; c <= m; c++) if(vis[c])
    {
        for(int i = 1; i <= m; i++)
        {
            int a1 = c * i, a2 = min(c * (i + 1) - 1, m); if(a1 > a2) break;
            for(int j = 1; j <= m; j++)
            {
                int b1 = c * j, b2 = min(c * (j + 1) - 1, m); if(b1 > b2) break;
                up(a1, c + 1); up(b1, c + 1);
                b[a1][b1] += i * j; b[a1][b2 + 1] -= i * j;
                b[a2 + 1][b1] -= i * j; b[a2 + 1][b2 + 1] += i * j;
            }
        }
    }
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= m; j++) b[i][j] += b[i][j - 1];
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= m; j++) b[i][j] += b[i - 1][j];
    unsigned int res = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= m; j++)
            if(i > j && vis[i] && vis[j]) res += (i / j) * b[i][j];
    cout << res << '\n';
    return 0;
}