【exgcd】“范式杯”2023牛客暑期多校训练营1 M

**范式杯**2023 牛客暑期多校训练营**一、题目描述**

在一个 $n times m$ 的矩阵中，给定一个矩阵 $A$ 和一个向量 $b$。要求找到满足方程 $Ax = b$ 的解。

**二、输入输出格式**

* 输入：两个整数 $n, m$，表示矩阵 $A$ 的行数和列数；接下来是 $nm$ 个整数，表示矩阵 $A$ 的元素；最后一个整数 $k$，表示向量 $b$ 中的元素个数；接下来是 $k$ 个整数，表示向量 $b$ 的元素。
* 输出：如果有解，则输出满足方程 $Ax = b$ 的解 $x$；否则输出 "-1"。

**三、代码实现**

cpp#include <iostream>
#include <vector>

using namespace std;

const int N =2e5 +10;
typedef long long ll;

ll n, m, k;
ll a[N], b[N];

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

void solve() {
 cin >> n >> m;
 for (ll i =1; i <= n * m; ++i) {
 cin >> a[i];
 }
 ll ans =0;
 for (ll i =1; i <= k; ++i) {
 cin >> b[i];
 ans += b[i] * a[i];
 }

 if (!ans) {
 cout << "-1
";
 return;
 }

 exgcd(n, m, n, m);
 ll x = (ll)((-b[1]) % n + n) % n;
 for (int i =2; i <= k; ++i) {
 b[i] += b[i -1] * x;
 if (b[i] >= n) {
 b[i] -= n;
 }
 }

 cout << x << " ";
 for (ll i =2; i <= k; ++i) {
 cout << b[i] << " ";
 }
}

int main() {
 ios::sync_with_stdio(false);
 cin.tie(0); cout.tie(0);

 int T =1;
 while (T--) {
 solve();
 }

 return0;
}