学步园

#include <stdio.h></p> <p>/*<br /> 函数名：gcdex<br /> 返回值: a,b的最大公约数<br /> 功能:求出a,b最大公约数，并且解出方程 a*u+b*v = gcd(a,b) u,v的值</p> <p>例子:<br /> 24 36<br /> 它们的公约数为12<br /> 12 = 24*(-1)+36*(1)<br /> */</p> <p>/*<br /> 程序的<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>依据：<br /> a%b = a-(a/b)*b<br /> 这个公式可以用矩阵表示出来</p> <p>| 0 1 | | a | | b | | m[i] |<br /> | 1 a/b | | b | = | a%b | = | n[i] |</p> <p>递推即可得出</p> <p>| 0 1 | …………| 0 1 | | 0 1 | | a | | b | | m[i] |<br /> | 1 m[i]/n[i] | …………| 1 m[2]/n[2] | | 1 m[1]/n[1] | | b | = | a%b | = | 0 |</p> <p>求出一下表达式第一行的两个元素的值，即是u,v</p> <p>| 0 1 | …………| 0 1 | | 0 1 |<br /> | 1 m[i]/n[i] | …………| 1 m[2]/n[2] | | 1 m[1]/n[1] |<br /> */</p> <p>int gcdex(int a,int b,int &u,int &v)<br /> {<br /> /*<br /> 构造的矩阵如图<br /> | u v |<br /> |temu temv|<br /> */<br /> int temp,temu=1,temv=-(a/b),p,q;<br /> u=0;<br /> v=1;<br /> while (1)<br /> {<br /> temp = b;<br /> b = a%b;<br /> a = temp;<br /> if(b == 0)<br /> break;<br /> p=u;q=v;<br /> u = temu;v = temv;<br /> temu = p+(-a/b)*temu;<br /> temv = q+(-a/b)*temv;<br /> }<br /> return a;<br /> }</p> <p>int main()<br /> {<br /> int a,b,tmp;<br /> int u,v;<br /> while(scanf("%d%d",&a,&b)!=EOF)<br /> {<br /> tmp=gcdex(a,b,u,v);<br /> printf("gcd is : %d = %d * (%d) + %d * (%d) /n",tmp,a,u,b,v);<br /> }<br /> return 0;<br /> }