扩展中国剩余定理

wjh15101051's space

卧薪尝胆，厚积薄发。

扩展中国剩余定理

Date: Sun Jul 01 10:26:01 CST 2018

In Category: 总结

求解不互质的同余模方程组。

已知：

$$ x\equiv a_1(mod\ n_1) $ $

$$ x\equiv a_2(mod\ n_2)$ $

$$\vdots$ $

$$x\equiv a_k(mod\ n_k) $ $

$x=a_1+k_1n_1$ $x=a_2+k_2n_2$

$a_1+k_1n_1=a_2+k_2n_2$

$k_1n_1-k_2n_2=a_2-a_1$

用扩展欧几里得求出方程的解 $k1,k2$ 。

也就得出了一个满足前两个方程的 $x$ 。

用 $x$ 模 $lcm(n_1,n_2)$ 求得 $a$ ，就得到了合并之后的方程 $x\equiv a(mod\ lcm(n_1,n_2))$


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

using namespace std;

long long t;

long long n;

long long a[8],m[8];

long long c;

long long res;

long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}

long long lcm(long long a,long long b)

{

    return a/gcd(a,b)*b;

}

long long exgcd(long long a,long long b,long long &x,long long &y)

{

    if(b==0)

    {

        x=1;

        y=0;

        return a;

    }

    long long x1,y1;

    long long w=exgcd(b,a%b,x1,y1);

    x=y1;

    y=x1-a/b*y1;

    return w;

}

void china()

{

    long long lcmi=m[1];

    for(long long i=2;i<=n;i++)

    {

        long long x,y;

        long long t=exgcd(m[i-1],m[i],x,y);

        long long w=a[i-1]+x*m[i-1]*(a[i]-a[i-1])/t;

        if((a[i]-a[i-1])%t){printf("Case %d: -1\n",c);return;}

        lcmi=lcm(m[i],m[i-1]);

        while(w<0)w+=lcmi;

        while(w>lcmi)w-=lcmi;

        m[i]=lcmi;

        a[i]=w;

    }

    res=(a[n]%lcmi+lcmi)%lcmi;

    if(res==0)res+=lcmi;

    printf("Case %d: %d\n",c,res);

    return;

}

int main()

{

    cin>>t;

    for(c=1;c<=t;c++)

    {

        scanf("%d",&n);

        for(long long i=1;i<=n;i++)

            scanf("%d",&m[i]);

        for(long long i=1;i<=n;i++)

            scanf("%d",&a[i]);

        china();

        res=0;

    }

    return 0;

}

In tag:

wjh15101051