信息
- ID
- 66
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
暴力枚举三元组即可。
注意到如果确定 i,j,那么 b 就确定了,就可以确定 ak 的值,于是只需要枚举 i,j 即可。
时间复杂度 O(n2)。
注意到 n 其实并不重要,相同的数是可以放到一起的。
考虑枚举 aj 的值,那么 ai 一定是其因子,于是根号枚举即可,时间复杂度 O(nV),V 是值域。
考虑根号分治,对于 ai≤V32 的时候根号暴力枚举,否则可以注意到 $b\le \lfloor \frac{V}{a_i} \rfloor \le V^{\frac{1}{3}}$,此时枚举 b 即可。
综上时间复杂度 O(nV31)。