记录编号	233189	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-03-04 10:43:39	内存使用	0.31 MiB

//KZNS
#include <fstream>
using namespace std;
//
ifstream fin ("mod.in");
ofstream fout ("mod.out");
//
int exgcd(int a, int b, int &x, int &y) {
	if (!b) {
		x=1;
		y=0;
		return a;
	}
	else {
		int u=exgcd(b, a%b, y, x);
		y-=a/b*x;
		return u;
	}
}
//
int main() {
	int a, b, x, y;
	fin >>a >>b;
	int u=exgcd(a, b, x, y);
	if (b>0) {
		if ((-x)>=0)
			u=(-x)/b+1;
		else
			u=(-x)/b;
	}
	else {
		if ((-x)>=0)
			u=(-x)/b;
		else
			u=(-x)/b+1;
	}
	fout <<x+b*u;
	return 0;
}
//UBWH