一元线性同余方程&&一元线性同余方程组

概述：求解一元线性同余方程以及一元线性同余方程组是拓展欧几里得算法的一个重要应用，以下是对问题所包含的几种情况向着拓展欧几里得算法转化的方法。

 一元线性同余方程(形如：a*x = b(mod m）)：

这种方程的求法可以转化成为一个不定方程：a*x-m*y=b,其结论同拓展欧几里得算法解不定方程，有解的充分必要条件是GCD(a,m)|b。解法直接套用相关拓展欧几里得算法，若想得到最小的整数解，那么令t=m/GCD(a,b),x=(x%t+t)%t即可，原理是只要我们找到一组特殊的解x0和y0那么我们就可以用 x0 和 y0 表示出整个不定方程的通解：

x=x0+(b/GCD(a,b))*t

y=y0-(a/GCD(a,b))*t

一元线性同余方程组：

对于一个一元线性同余方程组：

x=a1（mod m1）;

x=a2（mod m2）;

• ··

x=ak（mod mk）;

若有：

1. m1…mk之间两两互素，可以套用中国剩余定理(CRT)：

令M=m1*m2*…*mk，那么方程有解：X=a1*M1*M1^-1+a2*M2*M2^-1+…+ak*Mk*Mk^-1

其中Mi=M/mi,Mi^-1=Mi关于mi的乘法逆元。

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int q=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return q;
}
int CRT(int a[],int m[],int n){
    int M=1;int i;
    for(i = 0;i < n;i++)
    {
        M*=m[i];
    }
    int ret=0;
    for(i = 0;i < n;i++)
    {
        int x,y;
        int temp=M/m[i];
        exgcd(temp,m[i],x,y);
        ret+=temp*x*a[i]%M;
    }
    return (ret+M)%M;
}
int main(){
    int a[20],m[20];
    int n,i;
    cin>>n;
    for(i = 0;i < n;i++)
    {
        cin>>a[i]>>m[i];
    }
    cout<<CRT(a,m,n);
    system("pause");
    return 0;
}

2.若不满足如上条件，则可通过如下转化：

两两求算，如x=a1（mod m1）;x=a2（mod m2）;可分别按照一元线性同余方程组的转化方法写成如下形式：x=m1*y1+a1,x=m2*y2+a2。联立得到：m1*y1-m2*y2=a2-a1。同样的，可以直接套用拓展欧几里得算法，有解的充分必要条件是：GCD(m1,m2）|a2-a1。

y=xmod lcm(m1,m2);与下一个方程继续运算。

#include<iostream>
#include<stdio.h>
using namespace std;
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 q=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return q;
}
int main(){
    long long a1,c1,a2,c2,x,y,t;
    long long n;
    while(cin>>n){
        long long flag=1;
        cin>>a1>>c1;
        for(long long i=1;i<n;i++){
            cin>>a2>>c2;
            long long q=exgcd(a1,a2,x,y);
            if((c2-c1)%q!=0){
                flag=0;
            }
            t=a2/q;
            x=((x*(c2-c1)/q)%t+t)%t;
            //cout<<x;
            c1=c1+a1*x;
            a1=a1*(a2/q);
        }
        if(flag==0){
            cout<<"-1"<<endl;
            continue;
        }
        cout<<c1<<endl;
    }
    return 0;
}