題目大意：求一個同余方程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\n"); 35 } 36 else 37 { 38 printf("%lld\n",(x1*(s/ans)%(L/ans)+(L/ans))%(L/ans)); 39 } 40 return 0; 41 }

?

轉載于:https://www.cnblogs.com/yufenglin/p/10594049.html

總結

以上是生活随笔為你收集整理的康熙环球的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。