记录编号	233253	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-03-04 12:26:01	内存使用	0.29 MiB

#include<cstdio>
#include<cmath>
using namespace std;
const long c=1;
void ex_gcd(long a,long b,long& d,long& x,long& y){
	if(!b) {
		d=a;x=1;y=0;
	}
	else {
		ex_gcd(b,a%b,d,y,x);y-=x*(a/b);
	}
}
int main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	long a,b;
	scanf("%ld%ld",&a,&b);
	long x,y,d;
	ex_gcd(a,-b,d,x,y);
	x=x*c/d;
	long t=abs((-b)/d);
	while(x<=0) x+=t;
	printf("%ld",x);
	//printf("%d,%d,%d",x,y,d);
}