比赛链接

Solved by qxforever.

在半径为 $r$ 的圆内选 $n$ 个整点，使两两距离平方的和最大，输出答案。 $n\le 8$, $r\le 30$, $T\le250$

注意到 $n,r$ 的范围很小，输入最多有 $240$ 种情况，因此想到打表来解决此题。

首先所选的点一定在圆内整点形成的凸包上，如果不在凸包上，凸包上一定存在一点使答案更优。计算了一下 $r\in[1,30]$ 的凸包顶点数，发现最多为 $36$ 。在这些点中遍历答案即可，对每组 $(n,r)$，最多有 $\binom{36+8-1}{8}=1.45\times 10^8$ 种选择方案。本地需要 ~1 分钟可以打完。

注意在凸包上顶点很多的时候，也是有可能两个点重合的。一开始为了效率进行了这样的剪枝，导致 +2 。

感觉这里用概率算法并不是很好。

Solved by qxforever.

将 $n\times m$ 个数分组，使得存在能选出 $n$ 组 $m$ 个的方案以及 $m$ 组 $n$ 个的方案，最小化组数，输出字典序最大的方案。

将 $n,m$ 进行类似辗转相除的过程即可保证组数最小。

前缀平方和是完全平方数的正整数只有 $1$ 和 $24$

Solved by nikkukun & qxforever.

定义 Legeng Tuple 如下，

1. (1, k) 是
2. 如果 (n, k) 是，那么 (n + k, k) 也是
3. 如果 (n, k) 是，那么 (n * k, k) 也是

给定 $N,K$ ，问对任意 $1\le n\le N,1\le k \le K$ 一共有多少 Legeng Tuple。 $N,K\le 10^{12}$

分两种情况考虑

1. 进行过 *k 操作，那么可以表示为 p * k
2. 没有进行过 *k 操作，那么可以表示为 p * k + 1

答案是 $\sum_{i=1}^{k}(\lfloor\frac{n-1}{i}\rfloor+\lfloor\frac{n}{i}\rfloor +1)$ ，可以平方分块，也可以暴力算到 $\sqrt n$ ，后面就是一些 $0$ 和 $1$ 。