蓝桥杯 寻找整数

标签：11 frac gcd 寻找 整数 蓝桥 m1 m2 r1

题目
扩展中国剩余定理，将所有同余方程合并为一个
设有 \(x \equiv r_1(mod\ m_1)\)，\(x \equiv r_2(mod\ m_2)\)，即 \(x=m_1p+r_1=m_2q+r2\)

则有 \(m_1p-m_2q=r_2-r_1\)，

由扩展欧几里得算法，得：

方程 \(m_1p-m_2q=gcd(m_1,m_2)\) 特解 \(p',q'\)

对于原方程：

当 \((r2-r1)\%gcd(m_1,m_2)\neq0\) 时，无解。

特解： \(p^*=p'\times\frac{r_2-r_1}{gcd(m1,m2)}\)，\(q^*=q'\times\frac{r_2-r_1}{gcd(m_1,m_2)}\)

通解：

\[\left\{ \begin{aligned} &P=p^*+k\frac{m_2}{gcd(m_1,m_2)}\\ &Q=q^*-k\frac{m_1}{gcd(m_1,m_2)} \end{aligned} \right. \quad\quad\quad k\in Z \]

把通解 \(P\) 代入 \(x=m_1p+r1\) 中，得：

\[x=\frac{m_1m_2}{gcd(m_1,m_2)}k+m_1p'\frac{r_2-r_1}{gcd(m_1,m_2)}+r_1 \]

这样就将 \(2\) 个同余方程合成了一个了，这个式子同样可以继续和同余方程合并。

最终将所有同余方程合并为 \(1\) 个之后，取 \(x\) 得最小正整数解就行。

m = [i for i in range(2, 50)]
a = [1, 2, 1, 4, 5, 4, 1, 2, 9, 0, 5, 10,
     11, 14, 9, 0, 11, 18, 9, 11, 11, 15, 17, 9,
     23, 20, 25, 16, 29, 27, 25, 11, 17, 4, 29, 22,
     37, 23, 9, 1, 11, 11, 33, 29, 15, 5, 41, 46]

def exgcd(a, b):
    if b == 0: return a, 1, 0
    d, x, y = exgcd(b, a % b)
    x, y = y, x - a // b * y
    return d, x, y

def main():
    m1, r1 = m[0], a[0]
    for i in range(1, len(a)):
        m2, r2 = m[i], a[i]
        d, p, q = exgcd(m1, m2)
        if (r2 - r1) % d != 0: print(-1);return
        p *= (r2 - r1) // d
        p = (p % (m2 // d) + m2 // d) % (m2 // d) #保证p为正数
        r1 += m1 * p
        m1 *= m2 // d
    print(m1, r1)


if __name__ == '__main__':
    main()

标签：11,frac,gcd,寻找,整数,蓝桥,m1,m2,r1
From： https://www.cnblogs.com/BakaCirno/p/17899853.html