数论--模线性方程（组）

模板：

#include<bits/stdc++.h>
using namespace std;

//求x，y使得gcd(a,b)=a*x+b*y; 
int extgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;

   // cout<<x<<" "<<y<<endl;
    return d; // d =gcd(a,b);
}

//模线性方程 a * x = b (% n)
void modeq(int a, int b, int n) {
    int e,i,d,x,y;
    d=extgcd(a,n,x,y);
    if(b%d > 0) puts("No answer!");
    else {
        e = (x*(b/d))%n;
        for(i=0; i<d; i++) // !!! here x maybe < 0
            printf("%d-th ans: %d\n",i+1,(e+i*(n/d))%n);
    }
}


//  模线性方程组
int china(int b[], int w[], int k)
//b是模的值 w是余数的值 且 b和w互质 k是数组的长度  
{
    int i, d, x, y, m, a = 0, n = 1;
    for (i = 0; i < k; i++)
    {
        n *= w[i];  //  注意不能overflow
    }
    for (i = 0; i < k; i++)
    {
        m = n / w[i];
        d = extgcd(w[i], m, x, y);
        a = (a + y * m * b[i]) % n;
    }
    if (a > 0)
    {
        return a;
    }
    else
    {
        return (a + n);
    }
}

int main()
{
    int a,b,n,x,y;
    int t1[5]={3,5,7};
    int t2[5]={2,4,6};
    cin>>a>>b>>n;
    cout<<extgcd(a,b,x,y)<<endl;
    modeq(a,b,n);
    cout<<china(t2,t1,3)<<endl;
    return 0;
 }