例题: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;
}
标签:一次方程,gcd,多元,序列,include,扩欧,define
From: https://www.cnblogs.com/liqs2526/p/17550327.html