1楼：诺诺爱熊猫
//欧几米德算法 //算法描述：给定两个正整数m和n,求他们的最大公因子。 //1.
[求余数]用m除以n并令r为所得余数 //2.[余数为0]若r=0,则算法结束，n即为所求答案 //3.[互换]置m←n,n←r,并返回步骤1。
#include #include using namespace std; int main(int argc, char *argv) cout << m<< endl; system("pause"); return exit_success; }
麻烦采纳，谢谢!
扩展的欧几里得算法求逆元
2楼：匿名用户
数对 x，y ，使得 ***（a，b）=ax+by。
c++语言实现
#include
#include
using namespace std;
int x,y,q;
void extend_eulid(int a,int b)else
}int main()
你给的题目实际上就是： 给定 a 和b。
a 要有逆元 ， 那么***（ a ， b ) = 1假设a的逆元 为x ， 那么就有 a * x mod b = 1
也就是 a * x + b * y = 1上面的程序中输入a和b就可以求出对应的x和y。
其中 x 就是 a的逆元
扩展欧几里德算法是什么？
3楼：xhj北极星以北
扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = ***(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
下面是一个使用c++的实现：
intex***(int a,int b,int &x,int &y)
intr=ex***(b,a%b,x,y);
intt=x;x=y;y=t-a/b*y;
return r;
}把这个实现和***的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。
4楼：聪智宝贝
扩展欧几里德定理
对于不完全为 0 的非负
整数 a，b，***（a，b）表示 a，b 的最大公约数，必然存在整 数对 x，y ，使得 ***（a，b）=ax+by。
c++语言实现
#include using namespace std; int x,y,q; void extend_eulid(int a,int b) else } int main()
关于扩展欧几里得算法有点不明白，请大神指教
5楼：匿名用户
这是通过数学计算出来的（所以，学好数学很重要），其实你应该仔细理解该算法的原理！如下内容摘自：http:
//******blogs.***/frog112111/archive/2012/08/19/2646012.
html
扩展欧几里德算法
基本算法：对于不完全为 0 的非负整数 a，b，***（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 ***（a，b）=ax+by。
证明：设 a>b。
1，显然当 b=0，***（a，b）=a。此时 x=1，y=0；
2，ab!=0 时
设 ax1+by1=***(a,b);
bx2+(a mod b)y2=***(b,a mod b);
根据朴素的欧几里德原理有 ***(a,b)=***(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 *** 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
用c语言编制的求模逆元的扩展欧几里德算法，只要能基本上实现这个功能就行
6楼：匿名用户
** http://hi.baidu.***/forverlin1204/blog/item/dadfc612faddbfdbf6039e5f.html
#include
using namespace std;
//举例 3x+4y=1 ax+by=1
//得到一组解x0=-1，y0=1 通解为x=-1+4k,y=1-3k
inline __int64 extend_***(__int64 a,__int64 b,__int64 &x,__int64 &y)//ax+by=1返回a,b的***，同时求的一组满足题目的最小正整数解
ans=extend_***(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;
return ans;
}//(a/b)%mod=c 逆元为p，(p*b)%mod=1
//(a/b)*(p*b)%mod=c*1%mod=c
// (p*b)%mod=1 等价于 p*b-(p*b)/mod*mod=1其中要求p，b已知 等价于 ax+by=1
//其中x=p（x就是逆元）,y=p/mod,a=b,b=b*mod 那么调用extend_***(b,b*mod,x,y)即可求(a/b)%mod的逆元等价于a*p%mod
int main()
cout<<"x="< 1楼 猴大侠来也 你的程序是正确的， 瑕疵在于 scanf d d m n scanf函数，双引号内光写格式就好了，不用写逗号什么的，多写什么程序运行的时候就要输入什么。如你所写，运行时就应输入 12，24 若你在12与24之间按的是空格或其他有可能影响到第二个变量取不到值。 所以建议改为 scan...