多元一次方程的解（扩欧 + 构造）-526互联

例题：SGU 140

题意：

给出一个长度为 n 的非负整数序列 A 和两个数 P，B ，要求找出同样的非负整数序列 X 满足：
$A_1 * X_1 + A_2*X_2 + ... + A_n*X_n = B (mod P)$

思路：

看起来是一个多元一次方程，我们只需要找到一个合法的非负整数序列作为解即可，所以我们可以构造答案。我们可以求出二元一次方程的解，因此我们可以从前往后，两个数就可以找到一组解，这样两两合并即可得到一组合法的解。
即：先考虑$A_1 * X_1 + A_2*X_2$，我们可以求出方程：$A_1 * x + A_2 * y = gcd(A_1,A_2)$的解 x,y。此时 x 就是满足当前条件的 $X$ 序列的第一项的解，$X_1 = x, X_2 = y$。我们把 $ gcd(A_1,A_2)$ 当作新的元素，于是得到新的方程：
$gcd(A_1,A_2) * x + A_3 * X_3 + ... + A_n*X_n + P * Q = B$。
再继续合并$gcd(A_1,A_2)$ 和 $A_3$，求得方程：$gcd(A_1,A_2) * x + A_3 * y = gcd(gcd(A_1,A_2),A_3)$的解 x, y。则$X_3 = y, X_1 = X_1 * x, X_2 = X_2 * x$。
.......
这样不断递归最后就只剩下$gcd(A_1,A_2,,,A_n) * x + P * y = B$
最后再进行一次扩欧即可求出 $X$ 序列和 $gcd$。很明显，当 $gcd | B$ 时有解。最后答案输出注意取模为正。

AC代码：

// -----------------
//#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
#define rep(i,x,y) for(int i = (x); i <= (y); i ++)

using namespace std;

const int N = 100 + 7;
int A[N],X[N];
int n,p,b;

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

void solve()
{
    cin >> n >> p >> b;
    rep(i,1,n) cin >> A[i],A[i] %= p;
    // 求gcd(A1,A2,,,An) * x + A(n+1) * y = gcd(A1,A2,,,An,A(n+1))
    X[1] = 1;
    int gcd = A[1];
    for(int i = 2; i <= n; i ++)
    {
        int x,y;
        gcd = exgcd(gcd, A[i], x, y);
        // gcd的系数为 x,则前面所有的系数都得乘一遍 x,注意取模
        for(int j = 1; j < i; j ++) X[j] = X[j] * x % p; 
        X[i] = y;  // 新项的系数为 y
    }
    // 求gcd(A1,A2,,,An) * x + p * y = gcd(A1,A2,,,An,p) ? b
    int x,y;
    gcd = exgcd(gcd, p, x, y);
    for(int i = 1; i <= n; i ++) X[i] = X[i] * x % p;
    if(b % gcd == 0)
    {
        cout << "YES" << endl;
        for(int i = 1; i <= n; i ++)
        {
            X[i] = b * X[i] / gcd % p;
            cout << (X[i] + p) % p << " ";
        }
    }
    else cout << "NO" << endl;
}

signed main()
{
    IOS 
    int T = 1;
    //cin >> T;
    while(T --) { solve(); }
    return 0;
}