欧几里德与扩展欧几里德算法
|
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 |
#include<iostream> using namespace std; int maxGYS(int a,int b){ if(a%b==0){ cout<<b<<endl; return 0; } a=a%b; maxGYS(b,a); } int KZ(int a,int b,int a1=1,int b1=0,int a2=0,int b2=1){ int z=a/b; a1=a1-a2*z; b1=b1-b2*z; if(a%b==1){ return b1; } a=a%b; KZ(a,b,a2,b2,a1,b1); } int ZS(int a,int b){ a=a+b; if(a<0){ ZS(a,b); }else{ return a;} } int main(){ int a,b,c; cout<<"求最大公约数，请输入a,b"<<endl; cin >>a>>b; maxGYS(a,b); cout<<"扩展欧几里得"<<endl; cin >>a>>b; if(a<b){ c=a; a=b; b=c; } int x=KZ(a,b); x=ZS(x,a); cout<<x%a<<endl; return 0; } |
欣盅鼐97
2015年10月21日 07:04
[k]
欣盅鼐97
2015年10月21日 07:05
不错的~~! 感谢您提供