2024.8.5-A

T1 一切大师

algorithm:math

考虑将原式转换：

$$ \begin{aligned} ans &=\sum_{a=1}^{L}\sum_{b=1}^{L}[lcm(a,b)]*|ax-by|\\ &= \sum_{d=1}^{L}\sum_{a=1}^{\left \lfloor \frac{l}{d}\right \rfloor}\sum_{b=1}^{\left \lfloor \frac{l}{ad}\right \rfloor}[\gcd(a,b)=1]*d*|ax-by|\\ \end{aligned} $$

直接爆算，发现 TLE。

预处理 $\sqrt{L}$ 以内的 gcd ，再卡一下常，即可过掉。

T2 你考它干嘛

暂缺

T3 digital

喜闻乐见的模拟题

algorithm:divide-and-conquer

一个区间众数为 1，当且仅当 1 的个数大于等于 $\left \lfloor \frac{n+1}{2}\right \rfloor$。

考虑分治，设 solve(l, r, x) 表示区间 [l, r] 内有 x 个 1 是否可行。

则 solve(l, r, x) = OR_i = 0^x{AND{solve(l, mid, u = i), solve(mid + 1, r, x − i)}}

表示左区间有 i 个 1，右区间有 x − i 个 1。

特判特殊情况，再用 Hash 去重即可。

T4 代码之神 小Y

暂缺