https://www.luogu.org/problemnew/show/P1516#sub

?

題意還是非常好理解的.....

假如這不是一道環形的跑道而是一條直線，你會怎樣做呢？

如果是我就會列一個方程，像

$$x+m \times k = y+n \times k $$

求出方程解得k值。

然而這是一個環形跑道，也就有了取模的問題，然而我們只需要稍微改變一下方程

$$x + m \times k = y + n \times k + l \times z [z \in \mathbb{Z} ]$$

z表示被%掉了多少圈，我們試著兩邊轉移一下

$$(x-y)+(m-n) \times k = l \times z$$

我們定義$a=(x-y),b=(m-n)$

$$a +b \times k= l \times z $$

$$ bk+lz=a $$

那么我們的任務就變成了解出這個二元一次方程了。

首先判斷$ a是否整除gcd(b,l) $，不整除則無解，否則有解的話就可以用擴展歐幾里得求得解。

#include <algorithm> #include <iostream> #include <cstdio> using namespace std; #define LL long long LL xx,yy,n,m,x,y,a,b,l,r; LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b); } LL exgcd(LL a,LL b,LL &x,LL &y) {return !b?(x=1,y=0):(exgcd(b,a%b,y,x),y-=a/b*x); } int main() {cin>>xx>>yy>>m>>n>>l;a=xx-yy;b=n-m;if(b<0)b=-b,a=-a;r=gcd(b,l);exgcd(b,l,x,y);//現在我們解出的是bx+lz=gcd(b,l)的解，輸出答案是要擴大至a. if(a%r!=0)printf("Impossible");else cout<<((x*(a/r))%(l/r)+(l/r))%(l/r);//這個答案我研究了好久，最后才發現這個模數是因為組這么多步以后//他們兩個都回到了起始點. //cout<<x*(a/r); }

?

轉載于:https://www.cnblogs.com/rmy020718/p/9766469.html

總結

以上是生活随笔為你收集整理的洛谷 P1516 青蛙的约会的全部內容，希望文章能夠幫你解決所遇到的問題。

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