2529: 信息学奥赛一本通T1632-NOIP2012-同余方程

数学知识

这里其实就是在求数论逆元。数论逆元最常见的求法就是扩展欧几里得算法，实际上就是裴蜀定理。裴蜀定理的代码实现较为简单，这里提供两种编写方式 — 对应两种理解角度。
既然说到扩展欧几里得算法，自然跟欧几里得算法息息相关。欧几里得算法又称辗转相除法。接下来，我们看看如何理解。

角度 1 ：系数

由裴蜀定理可知现在，要求解的方程是 ax + by = 1，该式子等价于 ax % b = 1 % b，即代求方程。不做解释，就是最简单的变换 — 就是没啥好解释的。
由求解gcd的过程。或者说，欧几里得算法告诉我们以下方程式等价的，ax + by = bx’ + (a%b)y’ = 1。此时，需要找出 (x,y) 与 (x’,y’) 的关系。因为使用递归编写，所以x’,y’是已知的，现在通过x’,y’求得x,y。不妨令 y’ = x，那么 bx’ - (a//b)bx = by => x’ - (a//b)x = y。

/*
    以下代码使用 C++ 编写，C语言不存在软件级引用
 */
int exgcd(int a, int b, int& x, int&y) {
    int d = a;
    if (b != 0) {
        d = exgcd(b, a % b, y, x); // 求解出了 x', y' = x
        y -= a/b * x;
    }
    else {
        x = 1, y = 0;
    }
    return d;
}

角度 2： 等式

考虑到裴蜀定理说，a,b可以表示所有gcd(a,b)的倍数。所以a,b一定可以使用等式表达如：a + 0b = a; 0a + b = b;
而gcd的过程就转嫁到了等式右边单独进行，变换过程就成小学数学了。

int inverse(int number, int modulus) {
  int x1 = 1, y1 = 0;
  int x2 = 0, y2 = 1;
  int next_row = number % modulus;
  int times = number / modulus;
  int temp;
  while (next_row) {
    temp = x2;
    x2 = x1 - times * x2;
    x1 = temp;
    temp = y2;
    y2 = y1 - times * y2;
    y1 = temp;
    number = modulus;
    modulus = next_row;
    next_row = number % modulus;
    times = number / modulus;
  } 
  return x2;
}

代码实现

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include <iomanip>
#include <unordered_map>
#include <time.h>
inline void swap(int& num1, int& num2) {
  int temp = num1;
  num1 = num2;
  num2 = temp;
  return;
}
int inverse(int number, int modulus) {
  int x1 = 1, y1 = 0;
  int x2 = 0, y2 = 1;
  int next_row = number % modulus;
  int times = number / modulus;
  int temp;
  while (next_row) {
    temp = x2;
    x2 = x1 - times * x2;
    x1 = temp;
    temp = y2;
    y2 = y1 - times * y2;
    y1 = temp;
    number = modulus;
    modulus = next_row;
    next_row = number % modulus;
    times = number / modulus;
  } 
  return x2;
}
int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  int ans = inverse(a, b); // 求数论逆元
  ans = (ans + b) % b; // 保证是正数解
  printf("%d\n", ans);
  return 0;
}