Han Xin and His Troops（扩展中国剩余定理 Python版）

题目来源：2019牛客暑期多校训练营（第十场）

D - Han Xin and His Troops

题意：

看标题就知道大概了，韩信点兵的典故我们应该都熟悉吧。

给出 $n$ 个同余方程，问是否存在不超过 $m$ 的正整数解。

坑点：

数据比较大，直接用 CRT 会爆 ll，这时候就用 Python 来实现。

AC代码：

n = 110         # 同余方程个数

a = [0]*110     # 余数

m = [0]*110     # 模数

"""扩展欧几里得"""

def exgcd(a, b):

    if 0 == b:

        return 1, 0, a

    x, y, q = exgcd(b, a % b)

    x, y = y, (x - a // b * y)

    return x, y, q

"""扩展中国剩余定理"""

def CRT():

    if n == 1 :

        if m[0] > a[0]:

            return a[0];

        else:

            return -1;

    for i in range(n):

        if m[i] <= a[i] :

            return -1;

        x, y, d = exgcd(m[0], m[i])

        if (a[i] - a[0]) % d != 0:

            return -1;    

        t = m[i] // d;

        x = (a[i] - a[0]) // d * x % t

        a[0] = x * m[0] + a[0];

        m[0] = m[0] * m[i] // d;

        a[0] = (a[0] % m[0] + m[0]) % m[0]

    return a[0];

n, k = map(int, input().split())

for i in range(n):

    m[i], a[i] = map(int, input().split())

ans = CRT()

if ans==-1:

    print("he was definitely lying")

elif ans<=k:

    print(ans)

else :

    print("he was probably lying")

PS：扩展中国剩余定理似乎与中国剩余定理（CRT）关系不大，以下给出推导过程。

对于一组同余方程

\[ \begin{cases}
{x} \equiv {a_1} \text{ mod } {m_1}\\
{x} \equiv {a_2} \text{ mod } {m_2}\\
\dots\\\\
{x} \equiv {a_n} \text{ mod } {m_n}\\ \end{cases}\]

我们通过依次合并两组方程得到新的同余方程，这样经过 $n-1$ 次操作后，就能得到方程组的解。

首先对于前两组方程有：

\[ {x = a_1 + k_1m_1}\\
{x= a_2 + k_2m_2}\]

可得

\[{k_1m_1 - k_2m_2 = a_2-a_1}
\]

由扩展欧几里得，我们可以得到下面方程的解 ${x_0, y_0}$

\[{x_0m_1 - y_0m_2 = (m_1, m_2)}
\]

设 ${d = (m_1, m_2)}$

当且仅当 ${(a_2-a_1)} \text{ mod } {d = 0}$，方程有解。

所以

\[{x_0\frac{ a_2-a_1}{d}m_1 - y_0\frac{ a_2-a_1}{d}m_2 = a_2-a_1}
\]

所以我们得到 $k_1$ 的一组解为

\[k_1 = x_0\frac{ a_2-a_1}{d}
\]

方程的通解形式为

\[k_1 = k_1+n\frac{m_2}{d}\\
k_2 = k_2-n\frac{m_1}{d}\]

$k_1$ 的最小整数解为

\[k_1 = k_1\text{ mod } (m_2/d)
\]

代回原方程 $x = a_1+k_1n_1 $，我们得到 $x$ 的解以及 $a$.

此时方程组合并后的模数为

\[M = m_1*m_2/d
\]

因此原方程合并为

\[{x} = {a}\text{ mod } {M}
\]

巴特西

Han Xin and His Troops（扩展中国剩余定理 Python版）

Han Xin and His Troops（扩展中国剩余定理 Python版）

D - Han Xin and His Troops

题意：

坑点：

AC代码：

最新文章

热门文章