Descripion
岛上有 $m$ 个洞穴,顺时针编号为 $1 \sim m$ 。岛上有 $n\ (1 \leq n \leq 15)$ 个野人分别住在 $c_1,c_2,\ldots,c_n\ (1 \leq c_i \leq 100)$ 中。以后每年,第 $i$ 个野人会沿顺时针向前走 $p_i\ (1 \leq p_i \leq 100)$ 个洞住下来,其中第 $i$ 个野人可以生存 $l_i$ 年。没有 $2$ 个野人能在有生之年生存在同一个洞穴中,求洞穴个数 $m\ (m \leq 10^6)$ 的最小值。
Source
Solution
前置知识:
扩展欧几里得(exgcd)算法
对于 野人 $i$ 和 野人 $j$ $(i \neq j)$,假设经过 $x$ 天之后他们会在同一个洞穴相遇,那么可以得出方程:
化简方程,得到
这个方程等价于
显然我们可以用 exgcd(扩展欧几里得) 算法求出方程 $(p_i - p_j)x + m \times y = \gcd(p_i-p_j,m)$ 的一个解 $x’$ 。
如果 $\gcd(p_i-p_j,m) \nmid c_j-c_i$,说明 $x$ 无解,野人 $i,j$ 永远不会相遇。
若有解,我们求出 $x$ 的最小正整数解,即
如果 $x > \min(l_i,l_j)$,说明在他们相遇之前,$i, j$ 中会有至少一个野人死亡,所以也是可行的。
如果 $x \leq \min(l_i,l_j)$,说明 野人 $i,j$ 会在死亡前相遇,这个 $m$ 不可行。
我们只需要枚举每一个可能的 $m$(题目保证 $m \leq 10^6$),枚举每一对野人 $(i,j)$,用 exgcd 求解 $x$ 并判断这个 $m$ 是否满足要求。还有一些小细节:用 exgcd 时必须保证 $p_i \geq p_j$,因为 $\gcd$ 只对 非负整数 有意义。总时间复杂度为 $O( n^2m\log p_i)$ 。
Code
1 |
|