想要更好的阅读体验？

T3

给一个正整数环$A$,每次询问间隔$k$的数对乘积之和的最大值(你可以任意改变环的顺序)

$n,m\le 2\times 10^5$

简单的贪心:先考虑$gcd(n,k)=1$的情况:

最大的边上放第二大,第三大;第二大边上放第四大(已经在最大边上)

和暴力对拍下可知正确性

简单来说就是当前可选集合中最大的应该选尽量大的放在边上

比如说$a>b>c$,如果$(a,c,b)$那么贡献是$ac+bc$,而$(a,b,c)$贡献是$ab+bc$.因为$b>c$所以$ac>bc$.

对于不互质的情况,可以拆成$gcd(n,k)$个大小为$\frac{n}{gcd(n,k)}$的环,每个环如上处理即可.暴力做时间复杂度是$O(n^2)$,考虑相同的$gcd(n,k)$结果必然相同,记忆化一下就好了,时间复杂度$O(n\sqrt n)$

code