【扩欧】同余方程

$Sample$Sample $Input$Input

3 10

$Sample$Sample $Output$Output

7

$Train$Train $of$of $Thought$Thought

扩展欧几里得
（第一个题解的解释个人觉得比较好）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
ll x, y;
void init(ll a, ll b)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	init(b, a % b);
	ll c = x;
	x = y;
	y = c - a / b * y;
	return;
}
int main()
{
	ll a, b;
	scanf("%lld%lld", &a, &b);
	init(a, b);
	x = (x + b) % b;
	printf("%lld", x);
}