A sequence $A$ is called an integer sequence of length $N$ if all its elements $A_1, A_2, \ldots, A_N$ are non-negative integers less than $2000000000$. Consider two integer sequences of length $N, A$ and $X$. The result of their multiplication $(A \cdot X)$ is an integer number $R=\sum_{i=1}^N A_iX_i$. Your task is to solve the equation $A \cdot X \equiv B \pmod P$, given the integer sequence $A$ and the integer numbers $B$ and $P$.
题意概述
给定一个长度为$N$的向量$A$、两个整数$B, P$,求一个长度为$N$的向量$X$使得$A \cdot X \equiv B \pmod P$。向量中的数均为非负整数。
数据范围:$1 \le N \le 100, \ 0 \le B \lt P \le 10000$。
structIOManager { template <typename T> inlineboolread(T &x){ char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) returnfalse; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inlineboolread(char &c){ c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inlineintread(char s[]){ char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline IOManager operator > (T &x) { read(x); return *this; } template <typename T> inlinevoidwrite(T x){ if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } inlinevoidwrite(char c){ putchar(c); } inlinevoidwrite(char s[]){ int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } template <typename T> inline IOManager operator < (T x) { write(x); return *this; } } io;
structSolver { private: staticconstint N = 101; int n, p, m, a[N], x[N], y[N]; intex_gcd(int a, int b, int &x, int &y){ if (! b) { x = 1, y = 0; return a; } int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret; } voidinput(){ io > n > p > m; for (int i = 1; i <= n; ++ i) io > a[i], a[i] %= p; } voidprocess(){ int g = a[1]; x[0] = y[0] = 1; for (int i = 2; i <= n; ++ i) g = ex_gcd(g, a[i], x[i - 1], y[i - 1]); g = ex_gcd(g, p, x[n], y[n]); if (m % g) io < (char *) "NO\n"; else { io < (char *) "YES\n", g = m / g; for (int i = 1; i <= n; ++ i) { int t = g * (y[i - 1] + p); for (int j = i; j <= n; ++ j) t = 1ll * t * (x[j] + p) % p; io < t < ' '; } io < '\n'; } }