【拡張ユークリッド】POJ 1061+zoj 2657

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--------(y+ms)-(y+ns)=k*L化簡略化:k*L+(n-L)*s=x-y令a=L,b=n-m,n=x-y得ak+bs= bs=bs=b n;[ここでk,sは未知数であり、ax+by=n Egcd解析:(Egcdはax+by=gcd(a,b)を解くための(a,bは定数))方程式を解く手順:①:d=gcd(a,b)②:n%d!=0であれば、無解③:方程式の両側をdで同時に割ってa'k+b's=n'④:拡張ユークリッドEgcdでa'k+b's=1の解s⑤:得られた[s*n']方程式の1組の解⑥です:最も小さい非負の整数解を得て、型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
", y);
	}
	return 0;
}