首页 > 代码库 > 欧几里得？x

欧几里得？x

2024-09-16 04:47:50   208人阅读

1、欧几里得算法

带余除法定理：a，b∈Z，其中b>0，存在唯一q及r，使a=bq+r，其中0<=r<b;

辗转相除法(欧几里得算法)依据：(a,b)=(b,r)

C++实现：

 1 #include<iostream> 2  3 using namespace std; 4  5 int main() 6  7 { 8  9        int n,m,r;10 11        cin>>m>>n;12 13        r=m%n;14 15        while(r!=0)16 17        {18 19               m=n;20 21               n=r;22 23               r=m%n;24 25        }26 27        cout<<n;28 29 }

 

2.扩展欧几里得算法(裴蜀定理)

其中a，b是任意两个不全为0的整数，则存在两个整数x，y，使得ax+by=(a,b);

当(a,b)=1(互素)时，使ax+by=1;

应用：一次不定方程ax+by=c有解的充分条件是(a,b)|c；(|的意思是整除);

c++实现：

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4  5 using namespace std; 6  7 long long exgcd(long long a,long long b,long long &x,long long &y) 8 { 9     if(b==0)10     {11         x=1;12         y=0;13         return a;14     }15     long long r=exgcd(b,a%b,x,y),t=x;16     x=y;y=t-y*(a/b);17     return r; 18 }19 20 int main()21 {22     long long a1,b1,x1,y1;23     cin>>a1>>b1;24     exgcd(a1,b1,x1,y1);25     while(x1<0) x1+=b1;26     cout<<x1;27     return 0;28 }

 

欧几里得？x


联系
我们