看看注释

#include<cstdio>
#include<iostream>
using namespace std;
//const int MAXN=1e5+7;
//typedef unsigned long long ll;
typedef long long ll;
ll m,n,x,y,x2;//x,y,z;

ll exgcd(ll a,ll b)
{
	if(b==0)
	{
		x=1; y=0;
		//return a;
	}
	else 
	{
		exgcd(b,a%b);
		x2=x;
		x=y;
		y=x2-(a/b)*y;
		//cout<<x<<" "<<y<<" "<<a<<" "<<b<<endl;
	}
}
int main()
{
	cin>>m>>n;
	//cout<<gcd(m,n);
	//o=1%n;	
	/*for(int i=1;1;i++)
	{	//rubbish way 1
	    //o=n*i+1;
	    //if(o%m==0) 
	    //{
	       //cout<<o/m;	
		   //break;
	    //}
	    //rubbish way 2
	    //o=gcd(m*i,n);
	    /*if(o==0)
	    {
	   	   cout<<o;	
		   break;
	    }*/
	//way3
	    /*p=(m*i)%n;
	    if(p==o)
	    {
	    	cout<<i;
	    	break;
		}		
    }*/
    exgcd(m,n);
    cout<<(x%n+n)%n;
	return 0;
}