记录编号	331080	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2016-10-27 08:19:18	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
using namespace std;
int ex_gcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;return a;
	}
	int ret = ex_gcd( b , a%b , y ,x );
	y -= x * (a/b) ;
	return ret;
}
int a,b;
int main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	scanf("%d%d",&a,&b);
	int x , y , d = ex_gcd(a,b,x,y);
	while( x < 0 ) x += b ;
	printf("%d\n",x);
}