记录编号	345643	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	Twist Fate	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2016-11-11 13:40:08	内存使用	0.26 MiB

//第一题:数论 拓展欧几里得
//可以将原来的方程写成ax-1/b=y
//然后变一变就变成了ax-by=1  就是ax+b(-y)=1;
//所以需要a和b的最大公约数为1
//否则无解  但是拓展欧几里得是求最小解 不一定是整数的。。。
//所以我还是打暴力吧 
#include<cstdio>
#include<algorithm>
using namespace std;
int exgcd(int a,int b,int & x,int & y){
	int d=a;
	if(b==0){
		x=1,y=0;
	}
	else{
		d=exgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
	return d;
}
int main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	int a,b,x,y;
	scanf("%d%d",&a,&b);
	exgcd(a,b,x,y);
	while(x<0)x+=b;
	printf("%d\n",x);
	return 0;
}