int ExtendedEuclid( int f,int d ,int *result)
int main()
{
int n,b,z
z = 0
printf("输入两个数:\n")
scanf("%d%d",&b,&n)
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素,乘法的逆元是:谨厅%d\n",b,n,z)
else
printf("%d和%d不互素,最大公约祥档隐数为:%d\n",b,n,z)
return 0
}
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q
x1 = y2 = 1
x2 = y1 = 0
x3 = ( f>=d )?f:d
y3 = ( f>=d )?d:f
while( 1 )
{
if ( y3 == 0 )
{
*result = x3/* 两个数不互素则result为两个数的最大公约数,此时返回值为零 */
return 0
}
if ( y3 == 1 )
{
*result = y2/* 两个数互素则resutl为其乘法逆元,此时返回值为1 */
return 1
}
q = x3/y3
t1 = x1 - q*y1
t2 = x2 - q*y2
t3 = x3 - q*y3
x1 = y1
x2 = y2
x3 = y3
y1 = t1
y2 = t2
y3 = t3
}
}
/蠢厅*输入两个数:
5 14
5和14互素,乘法的逆元是:3
*/
采春宽用扩展欧几里德算法首先,欧几里德算法又称辗转相除法,用于求最大公约数,算法如下:
int Gcd(int a, int b)
{
if(b == 0)
return a
return Gcd(b, a % b)
}
扩展欧几里德算法能计算a模键改b及b模a的乘法逆元扒亮亮,如下:
int gcd(int a, int b , int&; ar,int &; br)
{
int x1,x2,x3;
int y1,y2,y3;
int t1,t2,t3;
if(0 == a)
{//有一个数为0,就不存在乘法逆元
ar = 0;
br = 0 ;
return b;
}
if(0 == b)
{
ar = 0;
br = 0 ;
return a;
}
x1 = 1;
x2 = 0;
x3 = a;
y1 = 0;
y2 = 1;
y3 = b;
int k;
for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)
{
k = x3 / y3;
t2 = x2 - k * y2;
t1 = x1 - k * y1;
x1 = y1;
x1 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
if( y3 == 1)
{
//有乘法逆元
ar = y2;
br = x1;
return 1;
}else{
//公约数不为1,无乘法逆元
ar = 0;
br = 0;
return y3;
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)