写在前面的话

感觉比以往的比赛难多了。出题人卡高精度，不好评价，但是题目还是好题。

考试的时候开题顺序为 \(T1-T3-T4-T2\) ，感觉和题目的实际难度排序差不多。

考试的时候懒了，没有去拼暴力，实际得分 \(80+0+100+0=180\) ,总体排名 \(rk 29\) 。

\(T1\)

题意简述

我们知道，对于一个整数 \(n\) , \(\lfloor \dfrac{n}{k}\rfloor\) 在 \(O(\sqrt n)\) 级别上。那么我们定义 \(f(n)\) 表示不同的 \(\lfloor \dfrac{n}{k}\rfloor\) 的个数。

有 \(T\) 次询问，每一次给出 \(n,m,k\) ，希望求出 \(\sum_{1\leqslant i \leqslant n ,i \bmod m=k} f(i)\) 。

对于 \(100 \%\) 的数据， \(T=5,n,m,k \leqslant 10^{13}\) 。

思路点拨

比较结论的一题，容易知道的是，在 \(1 \leqslant i \leqslant n\) 中， 不同的 \(f(i)\) 在 \(O(\sqrt n)\) 这个级别上。

我们可以预处理处每一个 \(f(i)\) 相同的连续段，这个是十分具有规律的，我们可以打表得出这个规律。

对于一组询问，我们可以暴力遍历这 \(\sqrt n\) 个连续段，我们对于一个连续段 \(l,r\) ，我们希望求出有多少个非负整数 \(x\) 满足 \(l \leqslant k+xm \leqslant r\) ,每一组合法的 \(x\) 会产生 \(f(l)\) 的贡献。

利用不等式的知识可以得出，\(k\) 的下界是 \(\lceil \dfrac{l-k}{m}\rceil\) ，上界是 \(\lfloor \dfrac{r-k}{m}\rfloor\) ,所以单次询问可以做到 \(O(\sqrt n)\) 。

期望得分 \(100\) ，但是本题需要高精度或者 int128 ，所以只有 \(80\) 。

\(T2\)

emm,看来这是本场最困难的题目。我实在是不会力！

\(T3\)

题目描述

现在有一个长度为 \(n\) 序列 \(\{a\}\) 以及一个常数 \(L\)，你需要构造长度为 \(n\) 的序列 \(\{x\}\) ,满足：

• \(x_i < a_i\) 。

• \(x_i \bmod L\) 的值互补相同。

问，有多少个序列 \(\{x\}\) 满足条件。