T1

100%

第一行输出 $n$ 个 #。

中间 $n-2$ 行，每行依次输出 #、$n-2$ 个空格、#。

第 $n$ 行输出 $n$ 个 #。

时间复杂度 $O(n^2)$。

T2

100%

用因式分解的方法找出 $N$ 所有的质因数，保存到数组 $B$。

设 $N$ 的质因数共 $cnt$ 个，如果 $cnt\geq 2$ 那么答案就是 $B[cnt-1]$，否则输出 $-1$。

时间复杂度 $O(\sqrt N)$。

T3

100%

先循环第一遍，统计数字 $x$ 在 $A$ 中的出现次数 $cnta[x]$。

然后循环第二遍，计算数组 $B$。

再循环第三遍，统计数字 $x$ 在 $B$ 中的出现次数 $cntb[x]$。

答案就是满足 $cntb[x]$ 最大的前提下，最大的 $x$。最后循环第四遍，找出答案。

注意：虽然四遍循环的范围都是 $1\sim n$，但是数组 $cnta$ 的规模需要开到 $10^7$。

时间复杂度 $O(n)$。

T4

40%

两重循环模拟 $k$ 次变异的过程，外层循环代表第几次变异，内层循环计算数位和，记得加上 $m$。

时间复杂度 $O(k\log(n))$。

60%

当 $n$ 的范围达到 $10^{100000}$，就需要用字符串的方式输入。

虽然 $n$ 的范围很大，但是变异一次后最多不超过 $\lg(n)\times 9+m\leq 2\times 10^6$，所以我们只需要对 $n$ 变异一次后的结果，再进行 $k-1$ 次变异就行了。

对于测试点#5~6，因为 $m=0$，所以当数字变异为个位数后，就不会再变化了。模拟 $k-1$ 次变异的过程，当变异为个位数时停止。

时间复杂度 $O(\log(n))$。

100%

$n$ 变异一次后最多不超过 $2\times 10^6$，所以即使 $k$ 的范围达到了 $10^{18}$，过程中出现的数字种类也不超过 $2\times 10^6$，也就是说当 $k>2\times 10^6$ 时变异过程会出现重复的部分。

记录 $t[x]$ 表示数字最早变异为 $x$ 是第几次操作的结果，当数字变异为一个之前出现过的数字 $y$ 时，从前一次变异为 $y$ 到本次变异为 $y$ 中间的过程就是接下来会不断重复的部分。计算这个部分的长度 $L$，将 $k-(t[y]+L)$ 对 $L$ 进行取模，余数部分继续模拟变异操作即可。

时间复杂度 $O(\log(n)+m\log(m))$。

T5

40%

用一重循环枚举除数 $i$，将 $N\mod i$ 加起来就是答案。

时间复杂度 $O(N)$。

100%

$N\mod i=N-\lfloor\frac{N}{i}\rfloor \times i$，所以 $\sum_{i=1}^N(N\mod i)=\sum_{i=1}^N(N-\lfloor\frac{N}{i}\rfloor \times i)=N^2-\sum_{i=1}^N\lfloor\frac{N}{i}\rfloor \times i$。

随着 $i$ 的增加，$\lfloor \frac{N}{i} \rfloor$ 是单调不增的，考虑将 $[1,n]$ 分为 $k$ 段 $[l_1, r_1], [l_2,r_2], \dots, [l_k,r_k]$，满足 $l_1 = 1, r_k = N, r_i + 1 = l_{i+1}(1\leq i\leq k-1)$，其中每一段 $[l_i, r_i](1\leq i\leq k)$ 都有：对于任意的 $x, y$ 满足 $x,y \in [l_i, r_i]$，都有 $\lfloor \frac{N}{x} \rfloor = \lfloor \frac{N}{y} \rfloor$；对于任意的 $x,y$ 满足 $x\in [l_i,r_i],y \notin [l_i,r_i]$，都有 $\lfloor \frac{N}{x} \rfloor \ne \lfloor \frac{N}{y} \rfloor$。令 $v_i=\lfloor \frac{N}{l_i} \rfloor$。

可以证明 $k\leq 2\times \sqrt{N}$，简要证明如下:

对于满足 $1\leq i\leq k,l_i \leq \sqrt{N}$ 的 $i$ 一定不超过 $\sqrt{N}$ 个，因为 $l_i$ 是两两不同的。

对于满足 $1\leq i\leq k, l_i \gt \sqrt{N}$ 的 $i$ 一定也不超过 $\sqrt{N}$ 个，因为 $l_i \gt \sqrt{N}$，所以有 $v_i \leq \sqrt{N}$，并且 $v_i$ 是两两不同的，所以满足条件的 $i$ 一定不超过 $\sqrt{N}$ 个。

所以一共最多不超过 $2\times \sqrt N$ 段。

答案即为 $N^2 - \sum_{i=1}^{k}(v_i \times \sum_{j=l_i}^{r_i}j)$，其中 $\sum_{j=l_i}^{r_i}j$ 可以通过等差数列求和公式 $O(1)$ 计算。

考虑当 $l_i(1\leq i \leq k)$ 确定后，如何快速的计算出 $r_i$，可以使用以下方法:

• 方法1：

因为随着 $i$ 的增加，$\lfloor\frac{N}{i}\rfloor$ 的值是单调不增的，所以可以通过二分的方法找到 $r_i$，其中 $r_i$ 就是最大的满足 $\lfloor\frac{N}{x}\rfloor = \lfloor\frac{N}{l_i}\rfloor$ 的 $x$。

时间复杂度 $O(\sqrt N\log(N))$。

• 方法2：

根据划分方法，$r_i$ 就是最大的满足 $\lfloor \frac{N}{x} \rfloor = v_i$ 的 $x$，这个是可以 $O(1)$ 计算出的，即 $r_i = \lfloor \frac{N}{v_i} \rfloor$。

时间复杂度 $O(\sqrt N)$。

T6

10%

用 $\text{DFS}$ 枚举知识点的复习顺序，计算所需的时间，对于符合条件的方案，维护最大价值和。

注意如果无法在 $t$ 时间内复习 $m$ 个知识点，要输出 $-1$。

时间复杂度 $O(n!)$。

30%

对于测试点#2~3，因为 $c_i=0$，所以只需要考虑选择复习哪些知识点，不需要考虑复习的顺序。

枚举每一个知识点是否选择，方案数不超过 $2^n$。

时间复杂度 $O(2^n)$。

结合第一部分可以拿到 $30\%$ 的分数。

50%

如果已经确定选择复习的知识点，考虑如何安排复习顺序能让花费的时间最少。此时只有 $c_i$ 对花费时间的贡献受顺序影响，按 $c_i$ 从大到小的顺序进行复习能让花费的时间最小。

因此先按 $c_i$ 从大到小的顺序将知识点排序，再枚举 $2^n$ 个方案即可。

时间复杂度 $O(2^n)$。

100%

按 $c_i$ 从大到小的顺序将知识点排序后，将知识点分为前 $\lfloor\frac{n}{2}\rfloor$ 个和后 $n-\lfloor\frac{n}{2}\rfloor$ 个两部分。

枚举前半部分的 $2^{\lfloor\frac{n}{2}\rfloor}$ 个方案，记录每个方案的花费时间和价值和，将选择了 $i$ 个知识点的方案存储到 $hans[i]$ 中，并进行处理，删去部分方案使得剩余方案都是对应价值和下花费时间最小的方案，具体来说：对于 $hans[i]$ 中任意两个方案 $A$ 和 $B$，如果 $A$ 的价值和小于等于 $B$ 的价值和，但 $A$ 的花费时间不小于 $B$ 的花费时间，那么删去方案 $A$，然后将剩余方案按花费时间排序。

具体实现上，可以将 $hans[i]$ 中的方案按花费时间排序，然后删去所有价值和没有递增的方案。

枚举后半部分的 $2^{n-\lfloor\frac{n}{2}\rfloor}$ 个方案，对于选择了 $i$ 个知识点的方案，则剩下 $m-i$ 个方案是在前半部分选择的，所以枚举时顺便维护选择的知识点的 $c_i$ 之和 $sumc$，花费时间 $nowt$ 应该增加 $sumc\times (m-i)$。然后在 $hans[m-i]$ 中用二分法，找出花费时间不超过 $t-nowt$ 的方案的最大价值和，加到当前方案的价值和上，然后用当前方案的价值和更新答案。

注意有可能出现 $hans[m-i]$ 中所有方案的花费时间都超过 $t-nowt$ 的情况。

时间复杂度 $O(n2^{n-\lfloor\frac{n}{2}\rfloor})$。