gcd(a,

gcd(a,
gcd(a,

gcd(a,
历史上第一个称得上算法的好像就是这个欧几里得算法,其实就是地球人都知道的辗转相除,不要小看她,她是很美的.
　　简单的描述就是,记gcd(a,b)表示非负整数a,b的最大公因数,那么：gcd(a,b)=gcd(b,a%b)或者gcd(a,0)=gcd(0,a)=a.
　　写成程序很简单,不管是用递归还是循环：
　　int gcd(int a,int b)
　　{
　　if(a==0)
　　return b;
　　if(b==0)
　　return a;
　　return gcd(b,a%b);
　　}
　　设有两个数num1和num2,假设num1比较大.令余数r = num1 % num2.
　　当r == 0时,即num1可以被num2整除,显然num2就是这两个数的最大公约数.
　　当r != 0时,令num1 = num2（除数变被除数）,num2 = r（余数变除数）,再做 r = num1 % num2.递归,直到r == 0.
　　以上数学原理可以用具体的两个数做一下分析,这样容易理解.
　　代码实现（求最大公约数）：
　　不仅算法形式简单,而且效率很高,我不知道具体是多少复杂度的,我只知道效率很高；）
　　前天看RSA算法,是非对称加密的标准算法,其实算法很简单：
　　找到两个素数p,q,再找一个数r,使gcd(r,(p-1)(q-1))=1,也就是说互素,然后再找一个数m,使rm=1(mod (p-1)(q-1)),然后再作乘法n=pq,然后把pq丢掉,最好是让任何人都不知道,包括自己（免得说梦话的时候被人听到）,然后手里拿到r,m,n,r就是Private Key,只有你知道,而m,n就是Public Key.设信息为a,加密过程：a^r=b (mod n),b就是密文,解密过程：b^m=a(mod n),反过来用m加密,用r解密是一样的.
　　书上说由gcd(r,(p-1)(q-1))=1到求m,使rm=1(mod (p-1)(q-1))是很容易的,就用辗转相除,我想了好久才想到一个方法.
　　问题：如果gcd(a,b)=1,求x,使ax=1(mod b)
　　由gcd(a,b)=1可知x是一定存在的,因为前式等同于：存在这样的x,y使ax+by=1,把by拿过去就是ax=-yb+1,即ax=1(mod b)
　　我令r0=a,r1=b,开始辗转相除
　　r0=q2r1+r2
　　r1=q3r2+r3
　　……
　　r(s-1)=q(s+1)r(s)+r(s+1),r(s+1)=1（一定存在着某个r(s+1)=1）
　　再把余数专门写到一边：
　　r0=a
　　r1=b
　　r2=r0-q2r1
　　r3=r1-q3r2
　　……
　　1=r(s+1)=r(s-1)-q(s+1)r(s)
　　后面的式子是关于前面的式子的多项式,而最开始是a和b,由最后一个式子就可以证明一定存在1=ax+by,它们都是关于a,b的一次多项式,那如何求x?把前面的式子代到后面,一个一个代,但是你会发现很复杂,不太容易求,于是我想到的就是同样的办法迭代.
　　设经过从前面的式子的代换,可以得到r(n)=x(n)a+y(n)b,那么有
　　r(n+1)=r(n-1)-q(n+1)r(n)
　　=x(n-1)a+y(n-1)b-q(n+1)(x(n)a+y(n)b)
　　=(x(n-1)-q(n+1)x(n))a+(...)b
　　于是得到x(n)的迭代式：x(n)=x(n-2)-q(n)x(n-1),同时有初值x0=1,x1=0,而q(n)=[r(n-2)/r(n-1)],于是x(n)是确定可求的.一个小小的问题是这样求出的x可能是负数,很简单,在mod b的情况下只需要加上b就行了.
　　代码：
　　#include
　　#include
　　int euc(int r1,int r2,int x1,int x2)
　　{
　　if(r2==1)
　　return x2;
　　if(r2==0)
　　return 0;
　　return euc(r2,r1%r2,x2,x1-r1/r2*x2);
　　}
　　int euclid(int a,int b)
　　{
　　assert(a>0&&b>0);
　　int x=euc(b,a%b,0,1);
　　if(x>a>>b;
　　x=euclid(a,b);
　　if(x==0)
　　cout