奶龙高手

题解题解 | #一日之计在于晨#

题解

/ 注册

题解 | #一日之计在于晨#

509 浏览 1 回复 2024-03-23

奶龙高手

+关注

一日之计在于晨

https://ac.nowcoder.com/acm/contest/77448/C

C 一日之计在于晨

刚开始，我们先对 $t$ 进行 $t=t-1$ 将时钟范围定为 $[0,m-1]$ ，

假设顺时针操作了 $x$ 次，那么最终位置在 $z\equiv t x*a\pmod m$

然后化为 $x*a\equiv z-t\pmod m$

此时是线性同余方程，然后化为 $a*x m*y\equiv z-t\pmod m$

同理，如果是逆时针操作 $x$ 次，那么方程为 $a*x m*y\equiv t-z\pmod m$

我们可以使用扩展欧几里得算法求解 $a*x_0 m*y_0\equiv\gcd(a,m)$ 的 $x_0$ 和 $y_0$

令 $d=\gcd(a,m)$

当 $z-t\equiv k*d\pmod m$ 时，线性同余方程才有解，

此时 $z=k*d t$ 且 $z∈[0,m-1]$ ，

我们需要 $z$ 尽可能小，如果 $k\geq0$ ，那么我们要刚好让 $z$ 到离 $m-1$ 最近的点再走一次，

也就是说 $k=\lfloor\dfrac{m-1-t}{d}\rfloor 1$

此时将方程两边同时乘上 $k$ ，得 $a*x_0*k m*y_0*k\equiv k*d$

令 $x_1=x_0*k,y_1=y_0*k$

有 $a*x_1 m*y_1\equiv k*d\pmod m$

此时 $x_1,y_1$ 是该方程的特解，我们需要求该方程的通解。

设 $x=x_1 z_1,y=y_1-z_2$ , 有 $a*(x_1 z_1) m*(y_1-z_2)\equiv k*d\pmod m$

解得 $\dfrac{z_1}{z_2}=\dfrac{a}{m}$ ，这个分式还可以化简，即 $\dfrac{z_1}{z_2}=\dfrac{\dfrac{a}{d}}{\dfrac{m}{d}}$

也就是说

\begin{cases} x=x_1\text{ }z*\dfrac{m}{d}\\ y=y_1\text{ }z*\dfrac{a}{d} \end{cases}

此时最小的非负整数解为 $x_1\mod \dfrac{m}{d}$

当 $t-z\equiv k*d\pmod m$ 时， $z\equiv t-k*d\pmod m$

同上，我们需要 $z$ 尽可能小，此时 $k=\lfloor\dfrac{t}{d}\rfloor$

再同上最小的非负整数解也为 $x_1\mod \dfrac{m}{d}$

此时求得

前者的同余方程的最小点为 $t (\lfloor\dfrac{m-1-t}{d}\rfloor 1)*d\mod m$ ，最小代价为 $(\lfloor\dfrac{m-1-t}{d}\rfloor 1)*x_0\mod \dfrac{m}{d}$

后者的同余方程的最小点为 $t-\lfloor\dfrac{t}{d}\rfloor*d\mod m$ ，最小代价为 $\lfloor\dfrac{t}{d}\rfloor*x_0\mod \dfrac{m}{d}$

C++

举报

收藏

赞 8

评论加载中...