poj 1061 扩展gcd解一元同余线性方程

对于同余线性方程，有如下的几个定理：

定理一：如果d = gcd(a, b)，则必能找到正的或负的整数k和l，使 d = a*x+ b*y。

定理二：若gcd(a, b) = 1，则方程ax ≡ c (mod b)在[0, b-1]上有唯一解。

定理三：若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。

定理三可以从定理二来进行证明，定理一和定理二是显然的。获得最小正整数解只需要对解进行简单的处理就行了。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 typedef long long ll;
 4 using namespace std;
 5 ll exgcd(ll a,ll b,ll &x ,ll &y)
 6 {
 7     if(b==0)
 8     {
 9         x=1;y=0;
10         return a;//返回的是gcd(a,b) 
11     }
12     ll ans=exgcd(b,a%b,x,y);
13     ll tmp=x;
14     x=y;
15     y=tmp-(a/b)*y;
16     return ans;
17 }
18 int main()
19 {
20     ll m,n,x,y,L;
21     while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L))
22     {
23         if(m==n)cout<<"Impossible
";
24         else
25         {
26             if(m<n)swap(m,n),swap(x,y);//保证方程中有a>0&&b>0
27             ll a=m-n;
28             ll c=y-x;
29             ll x1,y1;
30             ll d=exgcd(a,L,x1,y1);
31             if(c%d)cout<<"Impossible
";
32             else cout<<((c/d*x1+L/d)%(L/d)+L/d)%(L/d);//满足一元线性同余方程的最小正整数解 
33         }
34     }
35  }