251008 模拟赛

T1

直接马拉车即可，注意哪些地方不能取模，哪些地方需要取模；

\(100\to 40\)

T2

特判 \(n,k\le 2\) 的情况，其余情况一定有解；构造是简单的，扫两遍数组把数字填进去即可。

T3

死于不会 \(O(V\ln\ln V)\) 狄利克雷前缀和。

记 \(s(x)=\sum_{i=1}^{n}[x|a_i]a_i\)，那么答案为：

\[ \sum_{d|x}\frac{s(d)}{d}(\mu\cdot\operatorname{Id})(d) \]

证明考虑枚举 \(\gcd\)，然后莫反，其中点表示点乘，并非卷积。

先狄利克雷前缀和算出 \(s\)，然后线性筛 \(\mu*\operatorname{Id}\)，再跑一遍狄利克雷前缀和，即可做到 \(O(V\ln\ln V+q)\)。

当然，枚举约数也可以，时间复杂度 \(O\bigl((n+q)d(V)\big)\)。

T4

简单二维数点。