【扩张欧几里德】POJ 1061 + zoj 2657【更新时间2011-11-18】

【扩展欧几里德】POJ 1061 + zoj 2657【更新时间2011-11-18】
http://poj.org/problem?id=1061
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1657

两题一模一样，只是无解时输出情况不同
首先由题意有【x+ms与y+ns建立等价关系,设次数为s】：
x+ms ≡ (y+ns)(mol L)
->(x+ms)%L = (y+ns)%L
->((x+ms) - (y+ns))%L = 0
->(x+ms) - (y+ns) = k*L
化简得：
k*L + (n-m)*s = x-y
令a = L，b = n-m，n = x-y得
ak + bs = n;[其中k，s为未知数，形如ax + by = n

Egcd解析：


解方程步骤：
①：令d = gcd(a, b)
②：若n%d != 0，则无解
③：方程两边同时除以d ，得到a'k + b's = n'
④：用扩展欧几里德Egcd求出a'k + b's = 1的解s
⑤：得到的[s*n']就是方程的一组解
⑥：得到最小非负整数解，模a+a模a【求b的模a，求a的模b, 为什么？自己想】

#include <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL long long
#define inf 0x3fffffff

LL gcd (LL a, LL b)
{
	return b ? gcd (b, a%b) : a;
}

void Egcd (LL a, LL b, LL &x, LL &y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return ;
	}
	Egcd (b, a%b, x, y);
	LL tp = x;
	x = y;
	y = tp - a/b*y;
}

int main()
{
	LL xx, yy, a, b, x, y, L, n, M, N, d;
	while (~scanf ("%lld%lld%lld%lld%lld", &xx, &yy, &M, &N, &L))
	{
		a = L;
		b = N - M;
		n = xx - yy;
		d = gcd (a, b);
		if (n % d != 0)
		{
			puts ("Impossible");
			continue;
		}
		a /= d;
		b /= d;
		n /= d;
		Egcd (a, b, x, y);
		y *= n;
		if (a < 0) a = -a;    //周期是正的
		y = (y % a + a) % a;
		printf ("%lld\n", y);
	}
	return 0;
}