CF1830B

发布时间 2023-08-24 08:35:20作者: FOX_konata

原题

翻译

感觉挺好的题,但说不定挺典的?

我一开始想到了值域分块的思路,但之后就一直想整除、余数组合之类的。学数论学的

首先很容易想到\(\min{(a_i,a_j)} \leq \sqrt{2n}\),于是我们考虑枚举小的那个数

我们直接枚举小的\(a_i\)的值为\(k\),通过\(k\)我们可以找到所有\(a_i = k\)的位置

先考虑\(a_i = a_j = k\)的情况,我们枚举每个值为\(k\)的位置\(i\),我们可以得到满足条件的\(b_j = k^2 - b_i\),因此我们只需要对前缀\(a_i=k\)开一个桶,下标是\(b_i\)的值即可

然后考虑\(a_i = k < a_j\)的情况,我们枚举所有值\(>k\)的位置。我们现在易知的信息显然有:\(k\)\(a_j\)\(b_j\),我们可以求出\(b_i = k \times a_j - b_j\),我们同样可以用桶的思路找到所有\(a_i = k, b_i = k \times a_j - b_j\)的个数

最终复杂度\(O(n\sqrt{n})\)