题面:
思路:
a
⋅
x
=
b
⋅
y
+
1
a
⋅
x
−
b
⋅
y
=
1
因为y的取值是任意的,因此可以将这个式子看成:
a
⋅
x
+
b
⋅
y
=
1
因为题目保证有解,所以a和b是互质的,即
gcd
(
a
,
b
)
=
1
而扩展欧几里得就是用来求形如:
a
⋅
x
+
b
⋅
=
c
的不定方程的整数解的
这里需要再补充一个裴蜀定理:
若
a
,
b
为整数,那么一定存在
a
⋅
x
+
b
⋅
y
=
gcd
(
a
,
b
)
即
a
⋅
x
+
b
⋅
y
的值一定是
gcd
(
a
,
b
)
的倍数
先考虑边界情况
a
⋅
1
+
b
⋅
0
=
gcd
(
a
,
b
)
,
此时,
x
=
1
,
y
=
0
然后考虑一般情况,假设某一次得到的解是
x
0
、
y
0
b
⋅
x
0
+
(
a
m
o
d
b
)
⋅
y
0
=
gcd
(
a
,
b
)
b
⋅
x
0
+
(
a
−
⌊
a
b
⌋
⋅
b
)
⋅
y
0
=
gcd
(
a
,
b
)
a
⋅
y
0
+
b
⋅
(
x
0
−
⌊
a
b
⌋
⋅
y
0
)
=
gcd
(
a
,
b
)
由此可得:
x
=
y
0
,
y
=
x
0
−
⌊
a
b
⌋
⋅
y
0
已知任意一组解
x
0
,
y
0
通解为:
x
=
x
0
+
b
gcd
(
a
,
b
)
⋅
n
x
=
x
0
+
b
gcd
(
a
,
b
)
⋅
n
a\cdot x=b\cdot y +1\\ a\cdot x-b\cdot y =1\\ \text{因为y的取值是任意的,因此可以将这个式子看成:}\\ a\cdot x+b\cdot y =1\\ \text{因为题目保证有解,所以a和b是互质的,即}\gcd(a,b)=1\\ \text{而扩展欧几里得就是用来求形如:} a\cdot x+b\cdot=c\text {的不定方程的整数解的}\\ \text{这里需要再补充一个裴蜀定理:}\\ \text{若}a,b\text{为整数,那么一定存在}a\cdot x+b\cdot y=\gcd(a,b)\\ \text{即}a\cdot x+b\cdot y \text{的值一定是}\gcd(a,b)\text{的倍数}\\ \text{先考虑边界情况}a\cdot 1+b\cdot 0=\gcd(a,b),\text{此时,}x=1,y=0\\ \text{然后考虑一般情况,假设某一次得到的解是}x_0、y_0\\ b\cdot x_0+(a\bmod b)\cdot y_0=\gcd(a,b)\\ b\cdot x_0+(a-\lfloor \frac a b \rfloor\cdot b)\cdot y_0=\gcd(a,b)\\ a\cdot y_0+b\cdot (x_0-\lfloor \frac a b \rfloor\cdot y_0)=\gcd(a,b)\\ \text{由此可得:} x=y_0 ,y=x_0-\lfloor \frac a b \rfloor\cdot y_0\\ \text{已知任意一组解}x_0,y_0\text{通解为:} \\ x=x0+ \frac{b} {\gcd (a,b)}\cdot n\\ x=x0+ \frac{b} {\gcd (a,b)}\cdot n\\
a⋅x=b⋅y+1a⋅x−b⋅y=1因为y的取值是任意的,因此可以将这个式子看成:a⋅x+b⋅y=1因为题目保证有解,所以a和b是互质的,即gcd(a,b)=1而扩展欧几里得就是用来求形如:a⋅x+b⋅=c的不定方程的整数解的这里需要再补充一个裴蜀定理:若a,b为整数,那么一定存在a⋅x+b⋅y=gcd(a,b)即a⋅x+b⋅y的值一定是gcd(a,b)的倍数先考虑边界情况a⋅1+b⋅0=gcd(a,b),此时,x=1,y=0然后考虑一般情况,假设某一次得到的解是x0、y0b⋅x0+(amodb)⋅y0=gcd(a,b)b⋅x0+(a−⌊ba⌋⋅b)⋅y0=gcd(a,b)a⋅y0+b⋅(x0−⌊ba⌋⋅y0)=gcd(a,b)由此可得:x=y0,y=x0−⌊ba⌋⋅y0已知任意一组解x0,y0通解为:x=x0+gcd(a,b)b⋅nx=x0+gcd(a,b)b⋅n
代码:
#include
#include
using namespace std;
const int maxn=111111;
int a,b,x,y;
void exgcd(int a,int b,int *x,int *y)//扩展欧几里得算法
{
//cout<<"a="<
if(b==0)
{
*x=1,*y=0;
return;
}
exgcd(b,a%b,x,y); //r=GCD(a,b)=GCD(b, a%b)
//cout<<"!!!a="<
int t=*x;
*x=*y;
*y=t-a/b*(*y) ;
}
int main()
{
cin>>a>>b;
exgcd(a,b,&x,&y);
//cout<<"x="<
while(x<0) x+=b;
cout<<x<<endl;
return 0;
}