hexo-blog/source/_posts/oi/strange-way-to-express-integers.md

---

title: Strange Way to Express Integers tags:

• Bézout's Identity
• Chinese Remainder Theorem
• GCD-LCM
• Multiplicative Inverse id: "2182" categories:
• - OI
  • Number Theory date: 2018-03-04 21:00:27 ---

题目描述

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

• Choose $k$ different positive integers $a_1, a_2, \ldots, a_k$. For some non-negative $m$, divide it by every $a_i$ to find the remainder $r_i$. If $a_1, a_2, \ldots, a_k$ are properly chosen, $m$ can be determined, then the pairs $(a_i, r_i)$ can be used to express $m$.

"It is easy to calculate the pairs from $m$," said Elina. "But how can I find $m$ from the pairs?"

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

题意概述

给定同余方程组

$$ \left\{ \begin{array}{c} x \equiv r_1 \pmod{a_1} \\ x \equiv r_2 \pmod{a_2} \\ \cdots \\ x \equiv r_k \pmod{a_k} \end{array} \right. $$

求$x$的最小非负整数解。

数据范围：所有输入输出均可以表示为 64 位整型。

算法分析

对于两个方程

$$ \begin{align} x &\equiv r_1 \pmod{a_1} \\ x &\equiv r_2 \pmod{a_2} \end{align} $$

考虑将它们合并。易知

$$ x=r_1+k_1a_1=r_2+k_2a_2 $$

移项得

$$ k_1a_1=r_2-r_1+k_2a_2 $$

由贝祖定理可知，这个方程有整数解的充要条件为$(a_1, a_2) \mid r_2-r_1$。方程两边同时除以$(a_1, a_2)$

$$ \begin{align} k_1{a_1 \over (a_1, a_2)}&={r_2-r_1 \over (a_1, a_2)}+k_2{a_2 \over (a_1, a_2)} \\ k_1{a_1 \over (a_1, a_2)} &\equiv {r_2-r_1 \over (a_1, a_2)} \pmod{ {a_2 \over (a_1, a_2)}} \\ k_1 &\equiv \left( {a_1 \over (a_1, a_2)} \right)^{-1} \cdot {r_2-r_1 \over (a_1, a_2)} \pmod{ {a_2 \over (a_1, a_2)}} \end{align} $$

将其代回$x=r_1+k_1a_1$，得

$$ x \equiv r_1+k_1a_1 \pmod{ {a_1a_2 \over (a_1, a_2)}} $$

至此已成功将两个方程合并为一个相同形式的方程。

代码

/*
 * Your life would be very empty if you had nothing to regret.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

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

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y), (x += b) %= b;
}

signed main() {
  for (int k, a, r; ~scanf("%lld%lld%lld", &k, &a, &r);) {
    int flag = 0;
    for (int ai, ri; --k;) {
      scanf("%lld%lld", &ai, &ri);
      int gcd = get_gcd(a, ai);
      if ((r - ri) % gcd)
        flag = 1;
      r += get_inv(a / gcd, ai / gcd) * ((ri - r) / gcd) % (ai / gcd) * a;
      (a /= gcd) *= ai, ((r %= a) += a) %= a;
    }
    if (flag)
      puts("-1");
    else
      printf("%lld\n", r);
  }
  return 0;
}