记录编号	133972	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2014-10-28 23:45:26	内存使用	0.31 MiB

/*====================================================================================*/
/*==================================by Asm.Def========================================*/
/*====================================================================================*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <memory.h>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <ctime>
#include <iterator>
#include <functional>
#include <cstdlib>
using namespace std;
#define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it) 
#define pb push_back
#define REP(i,j,k) for(i = j;i <= k;++i)
#define REPD(i,j,k) for(i = j;i >= k;--i)
typedef long long LL;
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("mod.in","r");
FILE *out = fopen("mod.out","w");
#endif
template <typename T>inline void getint(T &x){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
}
/*===================================WORK============================================*/

void ex_euclid(int a, int b, int &x, int &y){
	if(!a){x = 0, y = 1;return;}
	ex_euclid(b % a, a, y, x);
	x -= (b / a) * y;
}

int main(){
	int a, b, x, y;
	getint(a), getint(b);
	ex_euclid(a, b, x, y);
	if(x <= 0)x += b;
	fprintf(out, "%d\n", x);
	//---------------------------------------------------------------------------------
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
	#endif
	return 0;
}
/*===================================================================================*/