\color{red}{更好的阅读体验}
更好的阅读体验
目录
1. 预习内容
1.1 阅读资料
1.2 练习题目
例题1 两个数的最大公约数
描述
输入2个正整数a，b，求a与b的最大公约数。
输入
2个正整数a，b，中间用空格隔开。(1<=a,b <= 104)
输出
输出a与b的最大公约数。
样例输入
6 15
样例输出
3
代码 1
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
int flag = 1;
for(int i = 2; i <= min(a,b); i++){
if(a % i == 0 && b % i == 0) flag = max(flag,i);
}
cout << flag << "\n";
return 0;
}
代码 2
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
return b ? gcd(b,a%b) : a;
}
int main(){
int a, b;
cin >> a >> b;
cout << gcd(a,b) << "\n";
return 0;
}
2. 课程内容
2.1 数论简介
数学题在算法竞赛中经常出现，在竞赛中经常把数学模型和其他算法结合起来，出综合性的题目。
分类
：
-
整除性问题:整除、最大公约数、最大公倍数;欧几里得算法、
扩展欧几里得算法
。 - 公式计算：高精度计算、概率和数学期望
- 素数问题:素数判定、筛法、区间素数统计。
- 同余问题:模运算、同余方程、快速幂、中国剩余定理、逆元、整数分解、同余定理、不定方程。
- 积性函数:欧拉函数、伪随机数、莫比乌斯反演。
- 多项式与生成函数：快速傅里叶变换、普通生成函数、指数生成函数。
- 递推关系:Fibonacci数列、Stirling数、Catalan数。
- 群论:Polya定理。
- 线性规划:单纯形法。
- 线性代数：矩阵、高斯消元。
- 博弈论：公平组合游戏、非公平组合游戏。
- 排列组合:容斥原理、抽屉原理、康托展开、排列生成、组合生成
特点
- 涉及大量数学定理、数学模型和公式计算，综合程度高
- 需要将题目抽象出其数学模型，或根据条件推理出规律进行求解
2.2 欧几里得算法
1. 简介与证明
概念
- 最大公约数指两个或多个整数共有约（因）数中最大的数
- 最小公倍数指两个或多个整数的公倍数里最小的数
-
欧几里得算法
：又称
辗转相除法
，用于计算两个
非负整数
aa
a
和
bb
b
的
最大公约数
思想
-
辗转相除法求最大公约数
求100和18的最大公约数？
-
1.令
a
0
=
100
，
b
0
=
18
⌊
a
0
b
0
⌋
=
5
，
a
0
−
⌊
a
0
b
0
⌋
×
b
0
=
10
2.
令
a
1
=
b
0
=
18
，
b
1
=
a
0
m
o
d
b
0
=
10
⌊
a
1
b
1
⌋
=
1
，
a
1
−
⌊
a
1
b
1
⌋
×
b
1
=
8
3.
令
a
2
=
b
1
=
10
，
b
2
=
a
1
m
o
d
b
1
=
8
⌊
a
2
b
2
⌋
=
1
，
a
2
−
⌊
a
2
b
2
⌋
×
b
2
=
2
4.
令
a
3
=
b
2
=
8
，
b
3
=
a
2
m
o
d
b
2
=
2
⌊
a
3
b
3
⌋
=
0
，
a
3
−
⌊
a
3
b
3
⌋
×
b
3
=
4
即最大公约数为
b
3
=
2
\begin{aligned} &1.令a_0=100，b_0=18\\\\ &\lfloor \frac{a_0}{b_0} \rfloor = 5，a_0-\lfloor \frac{a_0}{b_0} \rfloor\times b_0 = 10\\\\ &2.令a_1=b_0=18，b_1=a_0~mod~b_0=10\\\\ &\lfloor \frac{a_1}{b_1} \rfloor = 1，a_1-\lfloor \frac{a_1}{b_1} \rfloor\times b_1 = 8\\\\ &3.令a_2=b_1=10，b_2=a_1~mod~b_1=8\\\\ &\lfloor \frac{a_2}{b_2} \rfloor = 1，a_2-\lfloor \frac{a_2}{b_2} \rfloor\times b_2 = 2\\\\ &4.令a_3=b_2=8，b_3=a_2~mod~b_2=2\\\\ &\lfloor \frac{a_3}{b_3} \rfloor = 0，a_3-\lfloor \frac{a_3}{b_3} \rfloor\times b_3 = 4\\\\ &即最大公约数为b_3=2 \end{aligned}
1.
令
a
0
=
100
，
b
0
=
18
⌊
b
0
a
0
⌋
=
5
，
a
0
−
⌊
b
0
a
0
⌋
×
b
0
=
10
2.
令
a
1
=
b
0
=
18
，
b
1
=
a
0
m
o
d
b
0
=
10
⌊
b
1
a
1
⌋
=
1
，
a
1
−
⌊
b
1
a
1
⌋
×
b
1
=
8
3.
令
a
2
=
b
1
=
10
，
b
2
=
a
1
m
o
d
b
1
=
8
⌊
b
2
a
2
⌋
=
1
，
a
2
−
⌊
b
2
a
2
⌋
×
b
2
=
2
4.
令
a
3
=
b
2
=
8
，
b
3
=
a
2
m
o
d
b
2
=
2
⌊
b
3
a
3
⌋
=
0
，
a
3
−
⌊
b
3
a
3
⌋
×
b
3
=
4
即最大公约数为
b
3
=
2
求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
100 / 18 = 5 (余 10) 100%8=10
18 / 10= 1(余8) 18%10=8
10 / 8 = 1(余2) 10%8=2
8 / 2 = 4 (余0) 8%2=0
至此，最大公约数为2
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。
-
求
NN
N
和
MM
M
的最小公倍数
lc
m
(
N
,
M
)
lcm(N,M)
l
c
m
(
N
,
M
)
，则先求
NN
N
和
MM
M
的最大公约数
gc
d
(
N
,
M
)
gcd(N,M)
g
c
d
(
N
,
M
)
，然后
N×
M
g
c
d
(
N
,
M
)
\frac{N\times M}{gcd(N,M)}
g
c
d
(
N
,
M
)
N
×
M
则为最小公倍数。
2. 算法模板
//最大公约数
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
//最小公倍数
int lcm(int a,int b){
return a / gcd(a,b) * b;
}
3. 最大公约数
描述
输入两个正整数a、b，求a、b的最大公约数。要求采用递归函数实现。
输入
输入两个正整数a、b。
输出
输出a、b的最大公约数。
20 15
样例输出
样例输出
5
代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
return b ? gcd(b,a % b) : a;
}
int main(){
int a, b;
cin >> a >> b;
cout << gcd(a,b) << "\n";
return 0;
}
4. 多个数的最小公倍数
题目描述
输入n个数，请计算它们的最小公倍数。如5、7、15的最小公倍数是105。
输入
首先输入一个正整数T,表示测试数据的组数，然后是T组的测试数据。
每组测试先输入一个整数n（2<=n<=20),再输入n个正整数（n属于[1,100000]),这里保证最终的结果在int型范围内。
输出
对于每组测试，输出n个整数的最小公倍数。
样例输入
2
3 5 7 15
5 1 2 4 3 5
样例输出
105
60
分析
- 求多个数的最小公倍数，可以两两相求
代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
return b ? gcd(b,a % b) : a;
}
int lcm(int a,int b){
return a / gcd(a,b) * b;
}
void solve(){
int n;
cin >> n;
int t;
cin >> t;
for(int i = 2; i <= n ; i++){
int x;
cin >> x;
t = lcm(t,x);
if(i == n) cout << t << '\n';
}
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
2.3 扩展欧几里得算法
1. 简介与证明
作用
-
求形如
ax
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
a
x
+
b
y
=
g
c
d
(
a
,
b
)
的方程的解
x,
y
x,y
x
,
y
思想
-
欧几里得算法：
gc
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
gcd(a,b)=gcd(b,a\%b)
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
，特别的
gc
d
(
a
,
0
)
=
a
gcd(a,0)=a
g
c
d
(
a
,
0
)
=
a
-
裴蜀定理：对于任意正整数
a,
b
a,b
a
,
b
，一定存在非零的
x,
y
x,y
x
,
y
，使得
ax
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
a
x
+
b
y
=
g
c
d
(
a
,
b
)
-
{b
=
0
时
:
{
g
c
d
(
a
,
b
)
=
a
a
x
+
b
y
=
g
c
d
(
a
,
b
)
⇒
{
x
=
1
y
=
0
b
≠
0
时：
{
①
设
a
x
+
b
y
=
g
c
d
(
a
,
b
)
=
d
∵
由欧几里得算法可知：
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
=
d
∴
由裴蜀定理得：
b
x
′
+
(
a
%
b
)
y
′
=
d
又
∵
a
x
+
b
y
=
d
∴
联立
{
a
x
+
b
y
=
d
b
x
′
+
(
a
%
b
)
y
′
=
d
a
%
b
=
a
−
⌊
a
b
⌋
b
⇒
{
x
=
y
′
y
=
x
′
−
⌊
a
b
⌋
y
′
②
设
a
′
=
b
,
b
′
=
a
%
b
∴
g
c
d
(
b
,
a
%
b
)
=
g
c
d
(
a
′
,
b
′
)
=
d
∵
g
c
d
(
a
′
,
b
′
)
=
g
c
d
(
b
′
,
a
′
%
b
′
)
=
d
∴
b
′
x
′
′
+
a
′
%
b
′
y
′
′
=
d
又
∵
b
x
′
+
(
a
%
b
)
y
′
=
d
∴
联立
{
b
x
′
+
(
a
%
b
)
y
′
=
d
b
′
x
′
′
+
a
′
%
b
′
y
′
′
=
d
a
′
%
b
′
=
a
′
−
⌊
a
′
b
′
⌋
b
′
⇒
{
x
′
=
y
′
′
y
′
=
x
′
′
−
⌊
a
′
b
′
⌋
y
′
′
③
设
a
′
′
=
b
′
,
b
′
′
=
a
′
%
b
′
…
…
直到
b
=
0
时，联立解得
{
x
i
=
1
y
i
=
0
然后逐步返回每一次联立所得的结果
{
x
i
−
1
=
y
i
y
i
−
1
=
x
i
−
⌊
a
i
b
i
⌋
y
i
最后返回得到
x
和
y
的值
\begin{cases} b=0时:\begin{cases} gcd(a,b)=a\\ax+by=gcd(a,b)\\ \end{cases}\Rightarrow\begin{cases}x=1\\y=0\end{cases} \\ \\ \\ \\ \\ b\neq0时： \begin{cases} \begin{aligned} ①&设~ax+by=gcd(a,b)=d\\\\ &\because 由欧几里得算法可知：gcd(a,b)=gcd(b,a\%b)=d\\\\ &\therefore 由裴蜀定理得：b{x}’+(a\%b){y}’=d\\\\ 又&\because ax+by=d\\\\ &\therefore联立 \begin{cases} ax+by=d\\b{x}’+(a\%b){y}’=d\\a\%b=a-\lfloor\frac{a}{b}\rfloor b \end{cases}\Rightarrow\begin{cases}x={y}’\\y={x}’-\lfloor\frac{a}{b}\rfloor{y}’\end{cases}\\\\ ②&设{a}’=b,{b}’=a\%b\\\\ &\therefore gcd(b,a\%b)=gcd({a}’,{b}’)=d\\\\ &\because gcd({a}’,{b}’)=gcd({b}’,{a}’\%{b}’)=d\\\\ &\therefore {b}'{x}”+{a}’\%{b}'{y}”=d\\\\ 又&\because b{x}’+(a\%b){y}’=d\\\\ &\therefore联立\begin{cases} b{x}’+(a\%b){y}’=d\\{b}'{x}”+{a}’\%{b}'{y}”=d\\{a}’\%{b}’={a}’-\lfloor\frac{
{a}’}{
{b}’}\rfloor{b}’ \end{cases}\Rightarrow\begin{cases}{x}’={y}”\\{y}’={x}”-\lfloor\frac{
{a}’}{
{b}’}\rfloor{y}” \end{cases}\\\\ ③&设{a}”={b}’,{b}”={a}’\%{b}’\\\\ &\dots\\ &\dots\\ &直到b=0时，联立解得\begin{cases}{x}^i=1\\{y}^i=0\end{cases}\\\\ &然后逐步返回每一次联立所得的结果\begin{cases}{x}^{i-1}={y}^{i}\\{y}^{i-1}={x}^{i}-\lfloor\frac{
{a}^{i}}{
{b}^i}\rfloor{y}^{i} &最后返回得到x和y的值 \end{cases}\\ \end{aligned} \end{cases} \end{cases}
⎩
⎨
⎧
b
=
0
时
:
{
g
c
d
(
a
,
b
)
=
a
a
x
+
b
y
=
g
c
d
(
a
,
b
)
⇒
{
x
=
1
y
=
0
b
=
0
时：
⎩
⎨
⎧
①
又
②
又
③
设
a
x
+
b
y
=
g
c
d
(
a
,
b
)
=
d
∵
由欧几里得算法可知：
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
=
d
∴
由裴蜀定理得：
b
x
′
+
(
a
%
b
)
y
′
=
d
∵
a
x
+
b
y
=
d
∴
联立
⎩
⎨
⎧
a
x
+
b
y
=
d
b
x
′
+
(
a
%
b
)
y
′
=
d
a
%
b
=
a
−
⌊
b
a
⌋
b
⇒
{
x
=
y
′
y
=
x
′
−
⌊
b
a
⌋
y
′
设
a
′
=
b
,
b
′
=
a
%
b
∴
g
c
d
(
b
,
a
%
b
)
=
g
c
d
(
a
′
,
b
′
)
=
d
∵
g
c
d
(
a
′
,
b
′
)
=
g
c
d
(
b
′
,
a
′
%
b
′
)
=
d
∴
b
′
x
′′
+
a
′
%
b
′
y
′′
=
d
∵
b
x
′
+
(
a
%
b
)
y
′
=
d
∴
联立
⎩
⎨
⎧
b
x
′
+
(
a
%
b
)
y
′
=
d
b
′
x
′′
+
a
′
%
b
′
y
′′
=
d
a
′
%
b
′
=
a
′
−
⌊
b
′
a
′
⌋
b
′
⇒
{
x
′
=
y
′′
y
′
=
x
′′
−
⌊
b
′
a
′
⌋
y
′′
设
a
′′
=
b
′
,
b
′′
=
a
′
%
b
′
…
…
直到
b
=
0
时，联立解得
{
x
i
=
1
y
i
=
0
然后逐步返回每一次联立所得的结果
{
x
i
−
1
=
y
i
y
i
−
1
=
x
i
−
⌊
b
i
a
i
⌋
y
i
最后返回得到
x
和
y
的值
注意
-
当方程符合
ax
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
a
x
+
b
y
=
g
c
d
(
a
,
b
)
的形式时，才可以用扩展欧几里得算法求解
(x
0
,
y
0
)
(x_0,y_0)
(
x
0
,
y
0
)
-
**推论：**可以进一步求解任意方程
ax
+
b
y
=
n
ax+by=n
a
x
+
b
y
=
n
，得到一个整数解 -
{(
1
)
判断方程
a
x
+
b
y
=
n
是否有整数解，有解的条件为：
g
c
d
(
a
,
b
)
可以整除
n
(
2
)
用扩展欧几里得算法求
a
x
+
b
y
=
g
c
d
(
a
,
b
)
得到一个解
(
x
0
,
y
0
)
(
3
)
在
a
x
0
+
b
y
0
=
g
c
d
(
a
,
b
)
两边同时乘
n
g
c
d
(
a
,
b
)
⇒
a
x
0
n
g
c
d
(
a
,
b
)
+
b
y
0
n
g
c
d
(
a
,
b
)
=
n
(
4
)
对照
a
x
+
b
y
=
n
可知该方程的一个解为
(
x
′
,
y
′
)
，其中
{
x
′
=
x
0
n
g
c
d
(
a
,
b
)
y
′
=
y
0
n
g
c
d
(
a
,
b
)
\begin{aligned} \begin{cases} &(1)~~判断方程ax+by=n是否有整数解，有解的条件为：gcd(a,b)可以整除n\\\\ &(2)~~用扩展欧几里得算法求ax+by=gcd(a,b)得到一个解(x_0,y_0)\\\\ &(3)~~在ax_0+by_0=gcd(a,b)两边同时乘\frac{n}{gcd(a,b)}\Rightarrow\frac{ax_0n}{gcd(a,b)}+\frac{by_0n}{gcd(a,b)}=n\\\\ &(4)~~对照ax+by=n可知该方程的一个解为({x}’,{y}’)，其中\begin{cases}{x}’=\frac{x_0n}{gcd(a,b)}\\\\{y}’=\frac{y_0n}{gcd(a,b)} \end{cases} \end{cases} \end{aligned}
⎩
⎨
⎧
(
1
)
判断方程
a
x
+
b
y
=
n
是否有整数解，有解的条件为：
g
c
d
(
a
,
b
)
可以整除
n
(
2
)
用扩展欧几里得算法求
a
x
+
b
y
=
g
c
d
(
a
,
b
)
得到一个解
(
x
0
,
y
0
)
(
3
)
在
a
x
0
+
b
y
0
=
g
c
d
(
a
,
b
)
两边同时乘
g
c
d
(
a
,
b
)
n
⇒
g
c
d
(
a
,
b
)
a
x
0
n
+
g
c
d
(
a
,
b
)
b
y
0
n
=
n
(
4
)
对照
a
x
+
b
y
=
n
可知该方程的一个解为
(
x
′
,
y
′
)
，其中
⎩
⎨
⎧
x
′
=
g
c
d
(
a
,
b
)
x
0
n
y
′
=
g
c
d
(
a
,
b
)
y
0
n
2. 算法模板
void exgcd(int a, int b, int &x, int &y){
if(!b){ //若b=0时
x = 1,y = 0;
return ;
}
else{ //b!=0时
exgcd(b, a % b, x, y); //递归到下一层
int t = x; //返回时执行
x = y;
y = t - a / b * y;
}
}
3. 解ax+by=gcd(a,b)方程
描述
给定
n
n
n
对正整数
a
i
,
b
i
a_i,b_i
a
i
,
b
i
，对于每对数，求出一组
x
i
,
y
i
x_i,y_i
x
i
,
y
i
，使其满足
a
i
×
x
i
+
b
i
×
y
i
=
g
c
d
(
a
i
,
b
i
)
a_i×x_i+b_i×y_i=gcd(a_i,b_i)
a
i
×
x
i
+
b
i
×
y
i
=
g
c
d
(
a
i
,
b
i
)
。
输入格式
第一行包含整数
n
n
n
。
接下来
n
n
n
行，每行包含两个整数
a
i
,
b
i
a_i,b_i
a
i
,
b
i
。
输出格式
输出共
n
n
n
行，对于每组
a
i
,
b
i
a_i,b_i
a
i
,
b
i
，求出一组满足条件的
x
i
,
y
i
x_i,y_i
x
i
,
y
i
，每组结果占一行。
本题答案不唯一，输出任意满足条件的
x
i
,
y
i
x_i,y_i
x
i
,
y
i
均可。
数据范围
1
≤
n
≤
105
,
1≤n≤105,
1
≤
n
≤
105
,
1
≤
a
i
,
b
i
≤
2
×
1
0
9
1≤a_i,b_i≤2×10^9
1
≤
a
i
,
b
i
≤
2
×
1
0
9
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
代码
#include <bits/stdc++.h>
using namespace std;
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return ;
}
else{
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
int n;
cin>>n;
while(n--){
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
}
4. 解一元线性同余方程
概念
-
ax
≡
b
(
m
o
d
m
)
ax\equiv b(mod~m)
a
x
≡
b
(
m
o
d
m
)
，即
ax
m
\frac{ax}{m}
m
a
x
与
bm
\frac{b}{m}
m
b
的余数相同，且
a,
b
,
m
a,b,m
a
,
b
,
m
为整数，求
xx
x
的值 - 该方程即为一元线性同余方程
思想
-
对
ax
≡
b
(
m
o
d
m
)
ax\equiv b(mod~m)
a
x
≡
b
(
m
o
d
m
)
做等价变形：
ax
+
m
y
=
b
ax+my=b
a
x
+
m
y
=
b
-
∵a
x
≡
b
(
m
o
d
m
)
∴
a
x
%
m
=
k
(
b
%
m
)
,
(
k
∈
Z
)
∴
a
x
−
⌊
a
x
m
⌋
m
=
k
(
b
−
⌊
b
m
⌋
m
)
∴
a
x
−
k
b
=
(
⌊
a
x
m
⌋
−
k
⌊
b
m
⌋
)
m
∵
⌊
a
x
m
⌋
,
⌊
b
m
⌋
,
k
∈
Z
∴
(
⌊
a
x
m
⌋
−
k
⌊
b
m
⌋
)
∈
Z
设
(
⌊
a
x
m
⌋
−
k
⌊
b
m
⌋
)
=
y
,
(
y
∈
Z
)
∴
a
x
−
k
b
=
m
y
⇒
a
x
−
m
y
=
b
又
∵
y
可以为负数
∴
a
x
≡
b
(
m
o
d
m
)
↔
a
x
+
m
y
=
b
\begin{aligned} &\because &ax&\equiv b(mod~m)\\\\ &\therefore &ax\%m&=k(b\%m),(k\in \Z)\\\\ &\therefore &ax-\lfloor\frac{ax}{m}\rfloor m&=k(b-\lfloor\frac{b}{m}\rfloor m)\\\\ &\therefore &ax-kb&=(\lfloor\frac{ax}{m}\rfloor-k\lfloor\frac{b}{m}\rfloor)m\\\\ &\because &\lfloor\frac{ax}{m}\rfloor,&\lfloor\frac{b}{m}\rfloor,k\in \Z\\\\ &\therefore &(\lfloor\frac{ax}{m}\rfloor&-k\lfloor\frac{b}{m}\rfloor)\in \Z\\\\ &&设(\lfloor\frac{ax}{m}\rfloor&-k\lfloor\frac{b}{m}\rfloor)=y,(y\in \Z)\\\\ &\therefore &ax-kb&=my\Rightarrow ax-my=b\\\\ 又&\because &y&可以为负数\\\\ &\therefore &ax\equiv b(mod~&m)\leftrightarrow ax+my=b \end{aligned}
又
∵
∴
∴
∴
∵
∴
∴
∵
∴
a
x
a
x
%
m
a
x
−
⌊
m
a
x
⌋
m
a
x
−
kb
⌊
m
a
x
⌋
,
(⌊
m
a
x
⌋
设
(⌊
m
a
x
⌋
a
x
−
kb
y
a
x
≡
b
(
m
o
d
≡
b
(
m
o
d
m
)
=
k
(
b
%
m
)
,
(
k
∈
Z
)
=
k
(
b
−
⌊
m
b
⌋
m
)
=
(⌊
m
a
x
⌋
−
k
⌊
m
b
⌋)
m
⌊
m
b
⌋
,
k
∈
Z
−
k
⌊
m
b
⌋)
∈
Z
−
k
⌊
m
b
⌋)
=
y
,
(
y
∈
Z
)
=
m
y
⇒
a
x
−
m
y
=
b
可以为负数
m
)
↔
a
x
+
m
y
=
b
-
由扩展欧几里得算法的推论可知：当且仅当$ gcd(a,m)
可以整除可以整除
可以整除
b
时，时，
时，
ax+my=b$存在整数解 -
由扩展欧几里得算法可知：{
当
g
c
d
(
a
,
m
)
=
b
时：
{
x
=
x
0
y
=
y
0
当
g
c
d
(
a
,
m
)
为
b
的整数倍时：
{
x
′
=
x
0
b
g
c
d
(
a
,
m
)
y
′
=
y
0
b
g
c
d
(
a
,
m
)
由扩展欧几里得算法可知： \begin{cases} 当gcd(a,m)=b时：\begin{cases}x=x_0\\y=y_0\end{cases}\\\\ 当gcd(a,m)为b的整数倍时：\begin{cases}{x}’=\frac{x_0b}{gcd(a,m)}\\{y}’=\frac{y_0b}{gcd(a,m)}\end{cases} \end{cases}
由扩展欧几里得算法可知：
⎩
⎨
⎧
当
g
c
d
(
a
,
m
)
=
b
时：
{
x
=
x
0
y
=
y
0
当
g
c
d
(
a
,
m
)
为
b
的整数倍时：
{
x
′
=
g
c
d
(
a
,
m
)
x
0
b
y
′
=
g
c
d
(
a
,
m
)
y
0
b
例题 878. 线性同余方程
给定
n
n
n
组数据
a
i
,
b
i
,
m
i
a_i,b_i,m_i
a
i
,
b
i
,
m
i
，对于每组数求出一个
x
i
x_i
x
i
，使其满足
a
i
×
x
i
≡
b
i
(
m
o
d
m
i
)
a_i×x_i≡b_i(mod~m_i)
a
i
×
x
i
≡
b
i
(
m
o
d
m
i
)
，如果无解则输出
impossible
。
输入格式
第一行包含整数
n
n
n
。
接下来 $n $行，每行包含一组数据
a
i
,
b
i
,
m
i
a_i,b_i,m_i
a
i
,
b
i
,
m
i
。
输出格式
输出共
n
n
n
行，每组数据输出一个整数表示一个满足条件的
x
i
x_i
x
i
，如果无解则输出
impossible
。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在
int
范围之内。
数据范围
1
≤
n
≤
105
1≤n≤105
1
≤
n
≤
105
,
1
≤
a
i
,
b
i
,
m
i
≤
2
×
1
0
9
1≤a_i,b_i,m_i≤2×10^9
1
≤
a
i
,
b
i
,
m
i
≤
2
×
1
0
9
2
2 3 6
4 3 5
输出样例：
输出样例：
impossible
-3
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){
return b ? gcd(b,a % b) : a;
}
void exgcd(LL a,LL b,LL &x,LL &y){
if(!b){ //若b=0时
x=1,y=0;
return ;
}
else{
exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
int n;
cin>>n;
while(n--){
LL a,b,m,x,y;
cin>>a>>b>>m;
LL d=gcd(a,m);
exgcd(a,m,x,y);
if(b%d) cout<<"impossible"<<endl;
else cout<<b/d*x%m<<endl;
}
return 0;
}
3. 推荐阅读