ARC118 题解

[toc]

AC代码

A – Tax Included Price

询问第 $N$ 个无法被 $\frac{100+T}{100}\times i$ 表示的自然数（$i\in N^*$）。

$N\leq 10^9,T\leq 50$ 。

假设 $\frac{100+T}{100}\times i=j$ ，那么就已经存在 $j-i$ 个无法被表示的自然数，因此可以考虑二分搜索。

注意精度问题！全部使用整数计算，不要用浮点数！

B – Village of M People

给定两个正整数 $N,M$ 和一个大小为 $K$ 的数组 $A$ ，请你构造一个大小为 $K$ 的数组 $B$ 使得：

　$\sum_{i=0}^{K-1}A_i=N,\sum_{i=0}^{K-1}B_i=M$ ；

　最小化 $\max_i |\frac{A_i}{N}-\frac{B_i}{M}|$ 。

$N,M\leq 10^9, K\leq 10^5$ 。

由于浮点数运算精度不靠谱，考虑将上式乘上常数 $NM$ ，那么数组 $A$ 的每一项就变成了 $MA_i$ ，数组 $B$ 的每一项就变成了 $NB_i$ ，我们需要最小化 $\max_i|MA_i-NB_i|$ ，这样这个问题就可以通过整数运算解决了。

因为需要最小化 $\max_i |MA_i-NB_i|$ ，这可以考虑二分搜索一个偏差值 $x$ 使得 $MA_i-x \leq NB_i\leq MA_i+x$ ，每次check数组 $B$ 的和的最小、最大值是否包含 $M$ 。

C – Coprime Set

构造一个大小为 $N$ 的集合 $A$ 并满足：

集合 $A$ 中所有元素的最大公因数为 $1$ ；

集合 $A$ 中任意两个元素的最大公因数 $>1$ ；

每一项 $A_i$ 满足 $1\leq A_i\leq 10000$ 。

$3\leq N\leq 2500$ 。

考虑 $N=3$ 时的构造方案：$(6,10,15)$ ，然后我们可以向集合中不停加入形如 $6x,10y,15z$ 的整数即可，这样已经可以满足 $N\leq 2500$ 的数据范围了。

D – Hamiltonian Cycle

给定三个正整数 $P,A,B$ ，保证 $P$ 是质数，构造一个大小为 $P$ 的数列使得：

　$ A_i\leq P – 1$ 。

　$A_1 = A_P = 1$ 。

　$(A_1, A_2, \ldots, A_{P-1})$ 是 $(1, 2, \ldots, P-1)$ 的一个排列。

　对于任意的 $2\leq i\leq P$ 均至少满足以下任意一项：

　$A_{i} \equiv aA_{i-1}\pmod{P}$ 。

　$A_{i-1} \equiv aA_{i}\pmod{P}$ 。

　$A_{i} \equiv bA_{i-1}\pmod{P}$ 。

　$A_{i-1} \equiv bA_{i}\pmod{P}$ 。

$A,B<P\leq 10^5$ 。

相当有趣的一道题，关键是发现上方的限制实际上可以表示为：在一个网格图上，单元 $(i,j)$ 代表 $a^ib^j$ ，每次可以从 $(i,j)$ 走到与它四联通相邻的单元上，找一条起点为 $1$ 的不重复回路。

经过一些尝试后可以发现更强的性质：本题就是在一个 $n\times m(nm=P-1)$ 的网格图上找一条哈密顿回路，这个 $n\times m$ 的网格图的第一列可以这样构造：$g[i][0]=a^i\pmod{P}$ ，终点为 $g[n][0]=a^n\pmod{P}=1$（这意味着找到了一个循环节，返回了起点），因此 $m=\frac{P-1}{n}$ 。然后对于该网格图的每一项均有 $g[i][j]=g[i][j-1]\times B\pmod{P}(j>0)$ 。

以本题样例1 P = 13, A = 4, B = 5 为例，构造如下图：

如果无法构造出这个网格图，那么本题无解。

证明请参考 AtCoder官方题解，~~我纯靠脑补~~。

因此我们只需要想办法构造一个哈密顿回路即可，需要注意的一点是：在右边界向右走不一定会回到左边界上的同一行！只有上下边界是连通的！同时，由于 $P$ 是素数，所以 $P-1$ 是个偶数（特判2就好了），因此 $n,m$ 中至少有一个偶数，于是我们分类给出构造方案：

n,m=1
这时，网格图只有一行或一列，直接走到底就好。
n为偶数

如下图构造：
n为奇数

如下图构造：