extended_euclid.c

来自「简单的实现了数论中的乘法逆元 该代码均正确运行！包含运行图 及运行结果！」· C语言 代码 · 共 37 行

int Extended_Euclid(int f,int d)
{
	int T1,T2,T3,Q;
	int X[3]={1,0,f},Y[3]={0,1,d};
	while(Y[2]!=1)
	{
		if(Y[2]==0)
		return -1;		
	    Q=X[2]/Y[2];
		T1=X[0]-Q*Y[0];T2=X[1]-Q*Y[1];T3=X[2]-Q*Y[2];
		X[0]=Y[0];X[1]=Y[1];X[2]=Y[2];
		Y[0]=T1;Y[1]=T2;Y[2]=T3;	
	}
	if(Y[2]==1)
	{
		if(Y[1]<0)
		return Y[1]+f;
		else return Y[1];
		
	}
}
main()
{
	int f,d,i;
	printf("Please input two number:\n");	
	for(i=0;i<1;i++)
	{	
		scanf("%d,%d",&f,&d);
		/*if(d>f)
		{
			printf("The %d is less %d!Please input two number again!\n",f,d);
			i--;
		};*/
	}
	printf("%d在mod%d下有乘法逆元:%d",d,f,Extended_Euclid(f,d));
	
}