hexo-blog/source/_posts/oi/integer-sequences.md

---

title: Integer Sequences tags:

• Constructive Algorithm
• GCD-LCM id: "1628" categories:
• [OI, Common Skill]
• [OI, Number Theory] date: 2017-11-05 12:50:36 ---

题目描述

A sequence $A$ is called an integer sequence of length $N$ if all its elements $A_1, A_2, \ldots, AN$ 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$。

算法分析

设$g_i$表示$(A_1, A_2, \ldots, A_i)$，则有如下方程：

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

若$B \nmid (g_N, P)$，则无解；否则，解出所有$x_i, y_i$，即可还原出所有$X_i={B \over (gN, P)} \cdot y{i-1} \cdot \prod_{j=i}^N x_j$。

代码

#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;
}