http://poj.org/problem?id=1061

这题是大多大佬介绍完扩展欧几里得后拿来练习的。于是第一次做的时候就严格按照扩展欧几里得的办法，

x = x+k(c/gcd), y = y - k(c/gcd)了。

今天回过头来再看的时候发现还有一种处理负数的办法，就是在最后处理时先取模，再加模，再取模

第一步取模，使得到的答案绝对值小于模，加上模后使得值大于0但小于模

当时犯的错是都已经在0~模之间了，还要取模？

那是因为第三步是留给答案是正数的情况的（如果正数，取模再加模答案是大于等于模的，所以要再取模）

那么这样就完了？

当时纠结很久的是本题到底是对什么模，看一众blog都是说对L/gcd取模，太菜了没想出来

这个大佬的博客一个注释很微妙地。。我就懂了：https://blog.csdn.net/Littlewhite520/article/details/71155313/

原来还是借助扩展欧几里得的式子。

因为我们在这里求的是x，即蛙跳的次数。所以如果x小于0，按照式子我们就要不停的加c/gcd直到其大于0.

第一种方法就是不停地加，或者直接求int t = (x的绝对值/（c/gcd）,然后x+c/gcd*(t+1)即可

或者就是模它。。

代码贴下：

#include<stdio.h>
typedef long long ll;
ll gcd(ll a, ll b){
	if(!b) return a;
	return gcd(b, a%b); 
}
ll exgcd(ll a, ll b, ll &d, ll &x, ll &y){
	if(!b){d = a; x = 1; y = 0;}
	else{
		exgcd(b, a%b, d, x, y);
		ll temp = x;
		x = y;
		y = temp - (a/b)*y;
	}
	return d;
}
int main()
{
	ll x1, y1, m, n, t, L, q;
	scanf("%lld %lld %lld %lld %lld", &x1, &y1, &m, &n, &L);
	
	ll a = n-m, b = L, c = x1-y1, x, y, d;
	exgcd(a, b, d, x, y);
	
	if(c%d)
		printf("Impossible\n");
	else{
		x = x * (c / d);
		ll s = L/d;
		x = (x%s + s)%s; //这就是上文解释的
		printf("%lld\n", x);
	}
	return 0;
}