不错的根号分治练习题。
考虑枚举公差 \(k\)，题目就转化成了求 \(a_i - i \times k\) 相等的数的最大值。
考虑根号分治。
- 当 \(|k| \le \sqrt{10^5}\)，显然可以暴力枚举，开桶记录。
- 当 \(|k| > \sqrt{10^5}\)，对于一个 \(i\)，显然 \(a_i - i \times k = a_j - j \times k\) 的 \(i,j\) 离得不会太远，事实上 \(|i - j|\) 最大是大概 \(\sqrt{10^5}\)。仍然开桶暴力枚举即可。
综上，时间复杂度 \(O(n \sqrt{V})\)。
标签：Operations,10,传送门,CodeForces,sqrt,times,枚举,根号,Arithmetic From： https://www.cnblogs.com/zltzlt-blog/p/16758733.html