欧几里德和扩展欧几里德算法
分类:
IT文章
•
2023-11-29 20:33:55
先贴上资料：
1、http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html
2、http://blog.csdn.net/cqlf__/article/details/7953039
HDOJ 1108 最小公倍数
http://acm.hdu.edu.cn/showproblem.php?pid=1108
最小公倍数=两数相乘/最大公约数
用辗转相除法求最大公约数
![]()
1 #include<cstdio>
2 #define max(a, b) a > b ? a : b
3 #define min(a, b) a <= b ? a : b
4 int gcd(int a, int b)
5 {
6 int big = max(a, b);
7 int small = min(a, b);
8 int temp;
9 while(small != 0)//把小赋给大，把余数赋给小
10 {
11 temp = big % small;
12 big = small;
13 small = temp;
14 }
15 return big;
16 }
17
18 int main()
19 {
20 int a, b, ans;
21 while(scanf("%d%d", &a, &b) != EOF)
22 {
23 ans = a * b / gcd(a, b);
24 printf("%d
", ans);
25 }
26 return 0;
27 }
View Code
COJ 1124 最终时刻
http://122.207.68.93/OnlineJudge/problem.php?id=1124
求n个数的最小公倍数 long long即可
![]()
1 #include<stdio.h>
2 #define max(a,b) a>b?a:b
3 #define min(a,b) a>b?b:a
4 long long gcd(long long x,long long y)
5 {
6 long long da=max(x,y);
7 long long xiao=min(x,y);
8 long long rmd;
9 while(xiao!=0)
10 {
11 rmd=da%xiao;
12 da=xiao;
13 xiao=rmd;
14 }
15 return da;
16 }
17 int main()
18 {
19 int n;
20 long long ans,tmp;
21 while(~scanf("%d",&n))
22 {
23 scanf("%lld",&ans);
24 for(int i=1;i<n;i++)
25 {
26 scanf("%lld",&tmp);
27 ans=ans/gcd(ans,tmp)*tmp;
28 }
29 printf("%lld
",ans);
30 }
31 return 0;
32 }
View Code
COJ 1320 Scoop Water
http://122.207.68.93/OnlineJudge/problem.php?id=1320
不难发现结果是卡特兰数，如果选卡特兰数连乘和那个公式，不会有问题
但是我选的是h[n]=h[n-1]*(4*n-2)/(n+1)
这样在连乘取模的时候，因为有除法操作，得到的结果可能就不一样了，这时需要求(n+1)关于MOD的逆元，
然后拿乘积乘以此逆元才是正确结果 这个就是扩展欧几里德算法 里面的x，y分别是a关于b和b关于a的逆元
扩展欧几里德算法 只不过是在求解a、b最大公约数的时候顺便把逆元也求出来了 所以叫extendGCD
具体见代码：
![]()
1 #include <cstdio>
2 #define MOD 1000000007
3 #define MAXN 10010
4 int a[MAXN];
5 long long extgcd(long long a,long long b,long long &x,long long &y)
6 {
7 if(b==0)
8 {
9 x=1,y=0;
10 return a;
11 }
12 long long r=extgcd(b,a%b,x,y);
13 long long t=x;x=y;y=t-a/b*y;
14 return r;
15 }
16 void calcCATALAN(int n){
17 long long x,y;
18 a[1]=1;
19 int i;
20 for(i=2;i<n;++i){
21 x=a[i-1];
22 a[i]=(x*(4*i-2))%MOD;
23 extgcd(i+1,MOD,x,y);
24 x=(x+MOD)%MOD;
25 a[i]=(a[i]*x)%MOD;
26 }
27 }
28 int main()
29 {
30 calcCATALAN(MAXN);
31 int k;
32 while(scanf("%d",&k)!=EOF){
33 printf("%d
",a[k]);
34 }
35 return 0;
36 }
View Code
跟上题一样 依然套extgcd的模版就好了...
![]()
1 #include<cstdio>
2 #define LL long long
3 #define REP(i,a,b) for(int i=a;i<b;i++)
4 #define MAXN 100010
5 LL a[MAXN];
6 int n,m;
7 LL ext_gcd(LL a,LL b,LL &x,LL &y)
8 {
9 if(!b)
10 {
11 x=1; y=0;
12 return a;
13 }
14 LL r=ext_gcd(b,a%b,x,y);
15 LL t=x; x=y; y=t-a/b*y;
16 return r;
17 }
18 LL calc()
19 {
20 LL k=1;
21 REP(i,0,n) k=(k*a[i])%m;
22 return k;
23 }
24 void solve()
25 {
26 LL x,y,tot=calc();
27 REP(i,0,n)
28 {
29 ext_gcd(a[i],m,x,y);
30 x=(x+m)%m;
31 printf(i==(n-1)?"%lld":"%lld ",(tot*x)%m);
32 }
33 printf("
");
34 }
35 int main()
36 {
37 while(scanf("%d%d",&n,&m)!=EOF)
38 {
39 REP(i,0,n) scanf("%lld",&a[i]);
40 solve();
41 }
42 return 0;
43 }
