# Integer Sequences

## 题目描述

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$.

## 算法分析

\left\{ \begin{align} A_1x_1+A_2y_1&=g_2 \\ g_2x_2+A_3y_2&=g_3 \\ \cdots& \\ g_{N-1}x_{N-1}+A_Ny_{N-1}&=g_N \\ g_Nx_N+Py_N&=(g_N, P) \end{align} \right.

## 代码

#include <cctype>
#include <cstdio>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; 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> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(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;

struct Solver {
private:
static const int N = 101;
int n, p, m, a[N], x[N], y[N];
int ex_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;
}
void input() {
io > n > p > m;
for (int i = 1; i <= n; ++ i) io > a[i], a[i] %= p;
}
void process() {
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';
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot