Input
Output
Sample Input
1 2 3 4 5
Sample Output
4
这个题目是一个扩展欧几里得，一开始还没有看出来，自己的公式列错了，后来看出来之后，取模又没有取好，不过现在都解决了，
接下来我说一下这个题目的具体解题过程吧。
这个开始可以推得公式 n*t+y=x+m*t (mod l) 所以就可以化简成 (n-m)*t≡ x-y (mod l)
然后我们令a=n-m b=x-y
所以就可以转化成 a*t=b mod l
这个就是扩展欧几里得的求解 线性同余方程 的应用 这个不明白的可以看这个博客：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html
接下来说说线性同余方程过程
a*x≡b mod n
这个可以转化成 a*x+n*y=b (因为y不是需要得到的值，所以无所谓正负，不然这个应该是 a*x=n*y+b 换过去应该是有个负号的
然后你就会发现这个与扩展欧几里得的式子很像：a*x+n*y=gcd(a,n)
所以上面式子要求x，和下面式子求x，y差不多。
已知：如果一个方程a*x+b*y=c 如果gcd(a,b)|c 那么这个方程则有整数解，反之则没有。
所以我们要求整数解，那么说明gcd(a,n)|b 如果不整除，则说明输出Impossible
然后就很简单了，我们求出 扩展欧几里得的解，然后 就可以得到上式的解为 ans=x*b/gcd(a,n)
这个只是一个解，不一定是最小的正整数解，那么该如何取这个最小的正整数解呢？
定理二：若gcd(a, n) = 1，则方程ax ≡ c (mod n)在[0, n-1]上有唯一解。
定理三：若gcd(a, n) = d，则方程ax ≡ c (mod n)在[0, n/d - 1]上有唯一解。
这个是两个定理，具体证明过程请参照：
http://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html
由定理二可得，0~n-1上有唯一的解，但是这个又有点特别，因为这个的n值扩大了，需要缩小
缩小之后的结果就是在0~n/d-1 上有唯一的解，这个证明过程可以参照定理二的证明过程
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <string> #include <map> #include <cmath> #include <queue> #include <set> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const ll maxn = 3e10; ll exgcd(ll a,ll b,ll&x,ll&y) { if(b==0) { x = 1; y = 0; return a; } ll ans = exgcd(b, a%b, x, y); ll tmp = x; x = y; y = tmp - a / b * y; return ans; } int main() { ll x, y, m, n, l,s1,s2; cin >> x >> y >> m >> n >> l; ll a = n - m, b = x - y; ll d = exgcd(a, l,s1,s2); ll p = l / d; if(b%d!=0) { printf("Impossible\n"); return 0; } ll ans = (s1 * (b / d) % p+p)%p; printf("%lld\n", ans); return 0; }
然后再补充一个题：
S - C Looooops
for (variable = A; variable != B; variable += C)
statement;
Input
Output
Sample Input
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output
0 2 32766 FOREVER
这个题目和上面的一样的，所以就不说了，当作练习题练练手。
原文：https://www.cnblogs.com/EchoZQN/p/10692910.html