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^x_{i=0}\{AND\{solve(l,mid,u=i),solve(mid+1,r,x-i)\}\}\)

表示左区间有 \(i\) 个 \(1\)，右区间有 \(x-i\) 个 \(1\)。

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

T4 代码之神 小Y

暂缺