洛谷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;
}