9032
P9032 [COCI2022-2023#1] Neboderi 题解
P9032 考试题。 发现 \(g\) 的值是若干个相同的段,且段数很少,因为每次取 \(\gcd\) 至少会将值域变为原来的一半。所以段数是 \(\mathcal{O}(\log V)\) 的。 然后就可以从小到大枚举左端点,然后枚举 \(g\) 的值,找的是最远的满足 \(\gcd(a_l,\d ......
P9032 [COCI2022-2023#1] Neboderi
LuoguBlog 原题传送门 题意 给定 \(a\) 序列,一个区间的权值为区间 \(\gcd\) 乘上区间和,求长度 \(\ge k\) 的区间的最大权值。 \(1\le n,V\le 10^6\) 题解 区间 \(\gcd\) 相较于区间和更难维护,考虑枚举 \(\gcd\)。 记当前钦定的 ......