快乐的一天从AC开始 | 20210627 | CF1541B

题目链接
AC代码

每次看到形如(a_i + a_j = i + j)这种公式,总想着把带(i)的划到一边,带(j)的划到一遍,然后map乱搞。但是这题是(a_i cdot a_j = i + j),这样做并不行。

注意到一个非常重要的条件,就是(a)中元素是不重复的。所以可以用一个数组(p)记录(x)(a)中的下标。

然后对于每一个(a_i),从1开始枚举(a_j)的值,在根据(a_j)(p)获取其在(a)中的下标(j),然后就可以判断是否满足条件了。

因为(i + j le 2n),所以单次枚举的次数为(dfrac{2n}{a_i}),总的枚举次数为(2n sum_{i = 1}^{n} dfrac{1}{a_i}),由于(a_i)不重复,所以这是一个调和级数,总的枚举次数为(O(n log n))

原文地址:https://www.cnblogs.com/zengzk/p/14940472.html