扩展欧几里德和贝祖定理
概述
扩展欧几里德用来求解有关方程\(ax+by=m\)的问题
扩欧模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
return ans;
}
|
判断方程\(ax+by=m\)或\(ax≡m(mod\ b)\)是否有解
思路:当\(gcd(a,b)|m\)时 方程有解，反之则无解
求解方程\(ax+by=m( ax≡m(mod\ b) )\)的最小正整数解
思路
1.首先判断方程是否有解，无解则直接退出
2.扩欧求\(x\)，令\(bg=m/gcd(a,b),则x=(x\%bg+bg)\%bg\)
例1.洛谷 P1082 同余方程
题目描述
求关于x的同余方程ax≡1(mod b)的最小正整数解。
输入格式
一行，包含两个正整数a,b,用一个空格隔开。
输出格式
一个正整数x0，即最小正整数解。输入数据保证一定有解。
输入样例
输出样例
题解
模板题，由于题目规定一定有解，因此\(a⊥b（a与b互质）\) ，此时既可以用扩欧求解，也可用欧拉定理求解
在这科普一下欧拉定理：
\(a^φ(n) ≡1(mod\ n)(其中，a与n均为正整数，且两者互质。)\) 费马小定理为欧拉定理的特殊形式
代码
扩欧版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | #include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
return ans;
}
signed main()
{
int a,b;
int x,y;
cin>>a>>b;
exgcd(a,b,x,y);
x=(x%b+b)%b;
cout<<x<<endl;
return 0;
}
|
欧拉定理版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | #include<bits/stdc++.h>
using namespace std;
#define int long long
int qpow(int a,int n,int b)
{
int ans=1;
while(n)
{
if(n&1) ans=ans%b*a%b;
a=a%b*a%b;
n>>=1;
}
return ans;
}
int euler(int n)
{
int ans=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0) ans-=ans/i;
while(n%i==0) n/=i;
}
if(n>1) ans-=ans/n;
return ans;
}
signed main()
{
int a,b;
cin>>a>>b;
cout<<qpow(a,euler(b)-1,b)<<endl;
return 0;
}
|
例2.洛谷P5656 二元一次方程
题目描述
给定不定方程ax+by=c
若该方程无整数解，输出-1。
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中x的最小值，所有正整数解中y的最小值，所有正整数解中x的最大值，以及所有正整数解中y 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有整数解中x的最小正整数值，y的最小正整数值。
正整数解即为 x, y 均为正整数的解， 0 不是正整数。
整数解即为 x,y 均为整数的解。
x的最小正整数值即所有x为正整数的整数解中x的最小值，y同理。
输入格式
第一行一个正整数 T，代表数据组数。
接下来 T 行，每行三个由空格隔开的正整数a,b,c。
输出格式
T 行。
若该行对应的询问无整数解，一个数字 -1。
若该行对应的询问有整数解但无正整数解，包含 2个由空格隔开的数字，依次代表整数解中，x的最小正整数值，y 的最小正整数值。
否则包含5个由空格隔开的数字，依次代表正整数解的数量，正整数解中，x的最小值，y的最小值，x的最大值，y的最大值。
输入样例
| 7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432
|
| 4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74 | #include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
return ans;
}
signed main()
{
int t,a,b,c;
int x,y;
int minx,miny;
int maxx,maxy;
int cnt=1;
scanf("%lld",&t);
bool flag=false;
while(t--)
{
flag=false;
cnt=0;
scanf("%lld %lld %lld",&a,&b,&c);
int gcd=exgcd(a,b,x,y);
if(c%gcd)
{
cout<<"-1"<<endl;
continue;
}
int bg=b/gcd;
int cg=c/gcd;
int ag=a/gcd;
int tmp;
x*=cg;
y*=cg;
//cout<<"x= "<<x<<"y="<<y<<endl;
tmp=x;
x=(x%bg+bg-1)%bg+1;//最小正整数解 若是最小整数解则不用-1
int ansy=(y%ag+ag-1)%ag+1;
int t=(x-tmp)/bg;
y-=t*ag;
if(x>0&&y>0)
{
minx=x;
maxy=y;
flag=true;
cnt=1;
int k=y/ag;
if(y%ag==0)
{
cnt+=k-1;
miny=ag;
maxx=x+(k-1)*bg;
}
else
{
cnt+=k;
miny=y-k*ag;
maxx=x+k*bg;
}
}
if(flag) printf("%lld %lld %lld %lld %lld\n",cnt,minx,miny,maxx,maxy);
else printf("%lld %lld\n",x,ansy);
}
return 0;
}
|