JHwong

用户名：dotcpp0724243

访问量：834

签　名：

等　　级
排　　名	3391
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

蓝桥第7/8届练习题解
浏览：89

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

2529: NOIP2012-同余方程-了解即可

　　作者: JHwong　　　　发表时间：2024-02-07 17:21:06 浏览：34　|　评论：0　

原题链接：信息学奥赛一本通T1632-NOIP2012-同余方程

# 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。
```cpp
/*
    以下代码使用 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的过程就转嫁到了等式右边单独进行，变换过程就成小学数学了。
```cpp
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;
}
```

## 代码实现
```cpp
#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;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

2529: NOIP2012-同余方程-了解即可

评论区

精彩推荐

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-拆分位数（C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

数对（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

筛排处理（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

JHwong

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

2529: NOIP2012-同余方程-了解即可

评论区

精彩推荐

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-拆分位数 （C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

数对 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

筛排处理 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

　　评论区

WU-拆分位数（C++代码）

数对（C语言代码）

筛排处理（C语言代码）