记录编号	517625	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2018-10-27 21:02:46	内存使用	0.31 MiB

#include<bits/stdc++.h>
using namespace std;
int a,b,x,y,k;
void gcd(int a,int b)
{ if (b==0)
{ x=1;
  y=0;
  return;
}
 gcd(b,a%b);
 k=x;
 x=y;
 y=k-a/b*y;
 return;  
}
int main()
{ freopen("mod.in","r",stdin);
  freopen("mod.out","w",stdout);
  scanf("%d%d",&a,&b);
  gcd(a,b);
  printf("%d",(x+b)%b);
  return 0;
}