NEFU 84五指山

テーマリンク:http://acm.nefu.edu.cn/JudgeOnline/problem/84.jsp
考え方：前の問題とよく似ています。ユークリッドアルゴリズムを拡張します。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

typedef long long LL;

LL n, m, ax, by;

void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
	if(!b)
	{
		d = a; x = 1; y = 0;
	}
	else
	{
		ex_gcd(b, a%b, d, y, x);
		y -= x*(a/b);
	}
}

void read_case()
{
	scanf("%lld%lld%lld%lld", &n, &m, &ax, &by);
}

void solve()
{
	read_case();
	LL d, x, y;
	ex_gcd(m, n, d, x, y);
	if((by-ax) % d) { printf("Impossible
"); return ;}
	LL b1 = n / d;
	x *= (by-ax) / d;
	LL ans = (x % b1 + b1) % b1;
	printf("%lld
", ans);
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		solve();
	}
	return 0;
}