同余方程组问题

89 阅读 0 评论 59 点赞

我是靠谱客的博主沉默网络，这篇文章主要介绍同余方程组问题，现在分享给大家，希望可以做个参考。

*假设同余方程组

* x=a[1](mod m[1])

* x=a[2](mod m[2])
* .
* .
* .

* x=a[r](mod m[r])

*求解非负正整数解x

*思路：对于模线性方程组，在意进行方程组的合并，求出合并后的方程的解，这样就可以得出方程组的解，不管这样的方程有多少个，通过两两合并求得所有的解；因此，我们求*解的时候只要通过两个方程就可以了

* x=a[1](mod m[1])

* x=a[2](mod m[2])

*令mm=[m1,m2]

*首先，方程有解的充要条件是(m1,m2)|(b1-b2)，此时方程只有一个小于mm的非负整数解，利用扩展欧几里得算法就可以求出

*式1等价于x=a[1]+m[1]*y1;

*式2等价于x=a[2]+m[2]*y2;

*联立得到a[1]+m[1]*y1=a[2]+m[2]*y2，即m[2]*y2-m[1]*y1=b1-b2

*通过解一元线性方程可求解，再通过两两合并的思想来进行下一个方程

poj2891

题目连接：http://poj.org/problem?id=2891

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        d=a;
        return ;
    }
    ex_gcd(b,a%b,d,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
}

int main()
{
    ll k;
    ll a1,r1,a2,r2;
    ll a,b,c,d;
    ll x,y;
    bool flag;
    while(cin>>k)
    {
        flag=true;
        cin>>a1>>r1;
        for(ll i=1; i<k; i++)
        {
            cin>>a2>>r2;
            a=a1,b=a2,c=r2-r1;
            ex_gcd(a,b,d,x,y);
            if(c%d!=0)
            {
                flag=0;
            }
            a=a/d,b=b/d,c=c/d;
            x=(x*c%b+b)%b;
            r1+=a1*x;
            a1*=a2/d;
        }
        if(!flag)
        {
            cout<<-1<<endl;
            continue;
        }
        cout<<r1<<endl;
    }
    return 0;
}

hdu1573

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1573

*题意：满足同余方程组的x<m的个数
*
*思想：判断同余方程组在某个范围内的解的个数，在同余问题的基础上增加一个解不等式的过程，
*令A数组中所有数的最小公倍数是lcm，方程在lcm范围内的非负整数的解是a，则有a+lcm*x<=m,若a！=0，
*那么解的的x就是所求的个数，否则x-1就是解

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

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

ll ex_gcd(ll a,ll b,ll &x,ll&y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll r=ex_gcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

int rr[15],aa[15];
int main()
{
    ll t;
    ll n,m;
    ll lcm;//最小公倍数
    ll a,b,c,d;
    ll x,y;
    bool flag;
    cin>>t;
    for(int k=1; k<=t; k++)
    {
        cin>>m>>n;
        lcm=1;
        flag=true;
        for(int i=1; i<=n; i++)
        {
            cin>>aa[i];
            lcm=lcm/gcd(lcm,aa[i])*aa[i];
        }
        for(int i=1; i<=n; i++)
            cin>>rr[i];
        for(int i=2; i<=n; i++)
        {
            a=aa[1],b=aa[i],c=rr[i]-rr[1];
            d=ex_gcd(a,b,x,y);
            if(c%d!=0)
            {
                flag=false;
                break;
            }
            a=a/d,b=b/d,c=c/d;
            x=(x*c%b+b)%b;
            rr[1]+=aa[1]*x;
            aa[1]*=aa[i]/d;
        }
        if(flag==false)
        {
            cout<<"0"<<endl;
            //continue;
        }
        ll ans=0;
        if(rr[1]<=m)
            ans=1+(m-rr[1])/lcm;
        if(ans&&!rr[1])
            ans--;
        cout<<ans<<endl;
    }
    return 520;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

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

ll ex_gcd(ll a,ll b,ll &x,ll&y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll r=ex_gcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

int rr[15],aa[15];
int main()
{
    ll t;
    ll n,m;
    ll lcm;//最小公倍数
    ll a,b,c,d;
    ll x,y;
    bool flag;
    cin>>t;
    for(int k=1; k<=t; k++)
    {
        cin>>m>>n;
        lcm=1;
        flag=true;
        for(int i=1; i<=n; i++)
        {
            cin>>aa[i];
            lcm=lcm/gcd(lcm,aa[i])*aa[i];
        }
        for(int i=1; i<=n; i++)
            cin>>rr[i];
        for(int i=2; i<=n; i++)
        {
            a=aa[1],b=aa[i],c=rr[i]-rr[1];
            d=ex_gcd(a,b,x,y);
            if(c%d!=0)
            {
                flag=false;
                break;
            }
            a=a/d,b=b/d,c=c/d;
            x=(x*c%b+b)%b;
            rr[1]+=aa[1]*x;
            aa[1]*=aa[i]/d;
        }
        if(flag==false)
        {
            cout<<"0"<<endl;
            //continue;
        }
        ll ans=0;
        if(rr[1]<=m)
            ans=1+(m-rr[1])/lcm;
        if(ans&&!rr[1])
            ans--;
        cout<<ans<<endl;
    }
    return 520;
}

hdu3579

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3579

* 对于一个x，如果把x等分成n组，此时根据n的变化，可以得到不同的Mi和Ai，在这儿Mi表示每一次等
*分时一组的硬币数量，Ai表示等分后的余数
*
* 题意：给出n组Mi和Ai，求出x
*
* 思路：同余方程组的应用
*
* 这是典型的同余方程组的应用，但是要注意一点，题目要求输出最小的正整数解，如果所求的同余
*方程组的解为0，那么就应当输出Mi的最小公倍数
*

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

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

ll ex_gcd(ll a,ll b,ll &x,ll&y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll r=ex_gcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

int rr[15],aa[15];
int main()
{
    ll t;
    ll n;
    ll lcm;//最小公倍数
    ll a,b,c,d;
    ll x,y;
    bool flag;
    cin>>t;
    for(int k=1; k<=t; k++)
    {
        cin>>n;
        lcm=1;
        flag=true;
        for(int i=1; i<=n; i++)
        {
            cin>>aa[i];
            lcm=lcm/gcd(lcm,aa[i])*aa[i];
        }
        for(int i=1; i<=n; i++)
            cin>>rr[i];
        for(int i=2; i<=n; i++)
        {
            a=aa[1],b=aa[i],c=rr[i]-rr[1];
            d=ex_gcd(a,b,x,y);
            if(c%d!=0)
            {
                flag=false;
                break;
            }
            a=a/d,b=b/d,c=c/d;
            x=(x*c%b+b)%b;
            rr[1]+=aa[1]*x;
            aa[1]*=aa[i]/d;
        }
        cout<<"Case "<<k<<": ";
        if(flag==false)cout<<"-1"<<endl;
        else if(rr[1]!=0)cout<<rr[1]<<endl;
        else cout<<lcm<<endl;
    }
    return 520;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

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

ll ex_gcd(ll a,ll b,ll &x,ll&y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll r=ex_gcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

int rr[15],aa[15];
int main()
{
    ll t;
    ll n;
    ll lcm;//最小公倍数
    ll a,b,c,d;
    ll x,y;
    bool flag;
    cin>>t;
    for(int k=1; k<=t; k++)
    {
        cin>>n;
        lcm=1;
        flag=true;
        for(int i=1; i<=n; i++)
        {
            cin>>aa[i];
            lcm=lcm/gcd(lcm,aa[i])*aa[i];
        }
        for(int i=1; i<=n; i++)
            cin>>rr[i];
        for(int i=2; i<=n; i++)
        {
            a=aa[1],b=aa[i],c=rr[i]-rr[1];
            d=ex_gcd(a,b,x,y);
            if(c%d!=0)
            {
                flag=false;
                break;
            }
            a=a/d,b=b/d,c=c/d;
            x=(x*c%b+b)%b;
            rr[1]+=aa[1]*x;
            aa[1]*=aa[i]/d;
        }
        cout<<"Case "<<k<<": ";
        if(flag==false)cout<<"-1"<<endl;
        else if(rr[1]!=0)cout<<rr[1]<<endl;
        else cout<<lcm<<endl;
    }
    return 520;
}

* 如果m[1],m[2],……m[r]是两两互素的正整数，则同余方程组
* x=a[1](mod m[1])
* x=a[2](mod m[2])
* .
* .
* .
* x=a[r](mod m[r])
* 有模M=m[1]*m[2]*……m[r]的唯一解，这就是中国剩余定理
*
* 中国剩余定理的解题思想：令MM[i]=M/m[i],因为m[1],m[2]……m[r]两两互素，因此gcd(MM[i],m[i])=1;
*即MM[i]*P[i]=1(mod m[i]),那么：a[1]*MM[1]*P[1]+a[2]*MM[2]*P[2]+……a[r]*MM[r]*P[r]就是同余方程组的解

poj1006

题目连接：http://poj.org/problem?id=1006

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int m[4],a[4];
int mm;
void ex_gcd(int a,int b,int &d,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        d=a;
        return ;
    }
    ex_gcd(b,a%b,d,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
}

int china(int r)
{
    mm=1;
    int ans=0;
    int mi,d;
    int x,y;
    for(int i=1; i<=r; i++)
        mm*=m[i];
    for(int i=1; i<=r; i++)
    {
        mi=mm/m[i];
        ex_gcd(mi,m[i],d,x,y);
        ans=(ans+mi*a[i]*x)%mm;
    }
    if(ans<0)ans+=mm;
    return ans;
}

int main()
{
    int k = 0;
    int p,e,i,d;
    while(scanf("%d %d %d %d", &p, &e, &i, &d) != EOF)
    {
        k++;
        if(p==-1&&e==-1&&i==-1&&d==-1)
            break;
        a[1] = p, a[2] = e, a[3] = i;
        m[1] = 23, m[2] = 28, m[3] = 33;
        int ans = china(3);
            while(ans <=d)
                ans += mm;
            printf("Case %d: the next triple peak occurs in %d days.n", k, ans-d);

}
    return 520;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int m[4],a[4];
int mm;
void ex_gcd(int a,int b,int &d,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        d=a;
        return ;
    }
    ex_gcd(b,a%b,d,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
}

int china(int r)
{
    mm=1;
    int ans=0;
    int mi,d;
    int x,y;
    for(int i=1; i<=r; i++)
        mm*=m[i];
    for(int i=1; i<=r; i++)
    {
        mi=mm/m[i];
        ex_gcd(mi,m[i],d,x,y);
        ans=(ans+mi*a[i]*x)%mm;
    }
    if(ans<0)ans+=mm;
    return ans;
}

int main()
{
    int k = 0;
    int p,e,i,d;
    while(scanf("%d %d %d %d", &p, &e, &i, &d) != EOF)
    {
        k++;
        if(p==-1&&e==-1&&i==-1&&d==-1)
            break;
        a[1] = p, a[2] = e, a[3] = i;
        m[1] = 23, m[2] = 28, m[3] = 33;
        int ans = china(3);
            while(ans <=d)
                ans += mm;
            printf("Case %d: the next triple peak occurs in %d days.n", k, ans-d);

    }
    return 520;
}