问题描述:

给你一组形如下图的方程组:
EXCRT

你需要解出最小的$x$。

输入:

有多组数据,每组数据以$n$开始,表示有$n$个方程组
接下来n行分别表示$a_1$,$m_i$

输出:

输出最小的$x$

思路:

这就是扩展中国剩余定理的模板题了。如果$m_i$都两两互质,那么就是直接中国剩余定理就好了。但这里$m_i$是随机的,所以要用到一些其他的处理手法。

这里我们可以先用扩展欧几里得求出第一组方程:$x+y*m_1=a_1$。这样,我们得到了一组通解$x=x_0+t*m_1$。我们利用这组通解带入第二组方程,得到:$$x_0+t*m_1 \equiv a_2 (mod m_2)$$变形为:$$t*m_1 \equiv a_2-x_0 (mod m_2)$$于是我们得到了另一个线性同余方程,并且可以解出$t$的通解。利用这个通解又可以代入下一个方程。于是我们可以这样推出整个方程的解。

用数学归纳法再严谨地说一遍做法:设已经求出了$k$组方程,$ m_0= \prod_{i=1}^{k} m_i$,前$k$组方程的通解为$x=x_0+t*m_0$。那么我们可以将通解代入第$k+1$组方程中,得到$$t*m_0 \equiv a_{k+1}-x_0 (mod m_{k+1})$$
再利用扩展欧几里得解出新方程的通解。于是,我们可以利用$n$次扩展欧几里得解出计算出答案。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;

LL n, a[10000005], r[10000005];

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b==0)
    {
        x=1; y=0;
        return a;
    }
    LL d=exgcd(b, a%b, x, y);
    LL z=x; x=y; y=z-y*(a/b);
    return d;
}

LL solve()
{
    LL x=0, y=0, x0=0, m0=1;
    for(int i=1; i<=n; i++)
    {
        LL d=exgcd(m0, a[i], x, y);
        if((r[i]-x0)%d) return -1;
        x=(r[i]-x0)/d*x%a[i];
        x0=(x0+x*m0)%(m0/d*a[i]);
        m0=m0/d*a[i];
    }
    return (x0+m0)%m0;
}

int main()
{
    while(scanf("%lld", &n)!=EOF)
    {
        for(int i=1; i<=n; i++) scanf("%lld%lld", &a[i], &r[i]);
        printf("%lld\n", solve());
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注