康熙环球

题目大意：求一个同余方程tx+m≡ty+n (mod L)t的最小正整数解

首先我们可以把式子变形得到：t(x-y)≡(n-m) (mod L)

我们把(x-y)设为a，（n-m）设为s，可以得到ta≡s(mod L)

诶，好像比较熟悉啊，这就是同余方程的改进版。

我们可以先利用扩欧得到at+Ly=gcd(a,L)中t的一个特殊解t0，那么我们就可以把其他的解表示为t=t0+k*(L/gcd(L,a))

这个证明还是比较显然的，ax+by=c,ax0+by0=c

所以,a(x-x0)+b(y-y0)=0就是a(x-x0)=-b(y-y0)

将两边同除以gcd(a,b)得到a/gcd(a,b)*(x-x0)=-b/gcd(a,b)*(y-y0)

又因为a/gcd(a,b)与b/gcd(a,b)互质，所以为了保证式子的等价，显然b/gcd(a,b)整除（x-x0）所以上述结论成立

由于我们解得的t是at+Ly=gcd(a,L)中的t，所以我们要把它乘以s/gcd(a,L)，显然没有解的条件就是s%gcd(a,L)！=0

最后不要忘记是最小正整数，带入通向公式即可。%+%

最后，附上本题代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #define LL long long
 4 using namespace std;
 5 
 6 LL x,y,m,n,L,x1,y1,ans;
 7 
 8 LL exgcd(LL a,LL b,LL &x1,LL &y1)
 9 {
10     if(b==0)
11     {
12         x1=1;
13         y1=0;
14         return a;
15     }
16     ans=exgcd(b,a%b,x1,y1);
17     LL temp=x1;
18     x1=y1;
19     y1=temp-a/b*y1;
20     return ans;
21 }
22 int main()
23 {
24     cin>>x>>y>>m>>n>>L;
25     LL a=(m-n),s=(y-x);
26     if(a<0)
27     {
28         a=-a;
29         s=-s;
30     }
31     ans=exgcd(a,L,x1,y1);
32     if(s%ans!=0)
33     {
34         printf("Impossible
");
35     }
36     else
37     {
38         printf("%lld
",(x1*(s/ans)%(L/ans)+(L/ans))%(L/ans));
39     }
40     return 0;
41 }