A.solution

yywlp · 2024-03-29 17:43:47 · 题解

题解

一句话总结：阈值分块，整除分块。

观察数据范围发现 \sum\limits_{i=1}^{n}a_i 只有 10^9，我们设 A=\sum\limits_{i=1}^{n}a_i，在 B 把数分为两块，B_1\le B,B_2>B。

Part 1：B_1\times B_1

开个桶存一下每个数有多少个，B^2 枚举任意两个数算方案数即可。时间复杂度 \Theta(B^2)。

Part 2：B_2\times B_2

发现 B_2 最多只有 \frac{A}{B} 个数，又发现答案范围为：\frac{m}{B^2}。

那么我们枚举答案，再枚举 B_2 中的数，根据整除分块的知识即可求出另一个数的范围。

另一个数最大是 \frac{m}{B}，前缀和存一下就行。

时间复杂度 \Theta(\frac{A\times m}{B^3})。

Part 3：B_1\times B_2

这里我们把 B_1 中的数按 Q 分为 Q_1\le Q,Q_2>Q。

对于 Q_1,B_2，暴力枚举 Q_1 中数的大小，再枚举 B_2 中的每一个数，通过桶计算方案数即可，不过不要忘记对贡献 \times 2，因为每对数正反都会贡献一遍。时间复杂度 \Theta(\frac{A\times Q}{B})。

对于 Q_2,B_2，会发现答案范围为：\frac{m}{Q\times B} 依然枚举答案，枚举 B_2 中的数，根据整除分块算出范围，前缀和算方案数即可，这里和上一种一样，贡献也需要 \times 2。时间复杂度 \Theta(\frac{A\times m}{Q\times B^2})。

在通过整除分块算边界时有些细节需要稍微注意。

整体下来复杂度是 \Theta(B^2+\frac{A\times m}{B^3}+\frac{A\times Q}{B}+\frac{A\times m}{Q\times B^2})。稍微想一下发现 B=10^4,Q=10^3 的时候算出来大概是 3\times 10^8，可以通过。