euclid.cpp

欧几里德算法又称辗转相除法

//#define P printf//
#include<iostream.h>
//#include<stdio.h>//
#include<math.h>

void main()
{
    int d,f;
    int x_2=0,x_3,y_2=1,y_3,Q;
    int temp;
    cin>>d;
    cin>>f;
  
    x_3=d,y_3=f;
    while(y_3!=0&&y_3!=1)
    {
        Q=x_3/y_3;
    
        temp=y_3;
       
        y_3=x_3-Q*y_3;
    
        x_3=temp;
  
        temp=y_2;
       
        y_2=x_2-y_2*Q;
   
        x_2=temp;
      
  
    }


    if(y_3==0)
        cout<<"没有乘法逆元"<<endl;
    if(y_3==1)
    {
        y_2=(y_2+(abs(y_2/d)+1)*d)%d;
        cout<<f<<"mod"<<d<<"的乘法逆元是"<<y_2<<endl;
    }
    
    //getchar();//
   // getchar();//
    
}