[数据结构与算法]E - 乘法逆元（exgcd）

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Input

输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)

Output

输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Sample Input

2 3

Sample Output

2

题中的M,N就是a和p了，要求的k就是这里的x，显然，是个模板题，建议手模一下exgcd过程！！?

如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质)，则称a关于模p的乘法逆元为x。

贴个码就撤退：

#include<bits/stdc++.h>
using namespace std;
long long int i,j,d,k,a[3001011],t,n,p,x,y;
void exgcd(long long int a,long long int b,long long int &x,long long int &y){
	if(b==0){
		x=1;
		y=0;
		return ;
	}exgcd(b,a%b,x,y);
	t=x;
	x=y;
	y=t-(a/b)*y;
}
int main(){
	while(cin>>n>>p){
		exgcd(n,p,x,y);
		while(x<0){//算出来的x可能是个负的一直+p就好啦，这样子的正数x最小
			x+=p;}
			cout<<x<<endl;
	}
}