題意：中文題。。。
思路：由題意易知，posx + vx * t – posy – vy * t = k * L，也就是說解該方程的解。該方程經過化簡後可以寫為 t*(vx - vy) – k * L = posy – posx，進一步化簡為 k*L + t * (vy- vx) = posx – posy,L和(vx - vy)都可以求出來，也就是說是已知的。該方程是我們比較熟悉的，也就是常見的擴展歐幾裡得方程的形式。
此時，令 gcdx = gcd(L,vy - vx)，若(posx – posy) % gcdx == 0,則該方程有解，也就是說青蛙可以碰見，否則是碰不到的。
接下來運用擴展歐幾裡得就可以了，至於擴展歐幾裡得的知識，網上有很多，這裡就不多說了。當我們用擴展歐幾裡得求出ax + by = 1的一組解後，我們需要求最小的正整數解。對題目來說，就是t必須為正整數，若求出的特解為負數，這時我們需要處理一下。
ax + by = pos 此時又一組解，其中y是負數。我們的目的是使得y變為滿足方程的最小正數。現在我們把方程改變一下。ax – kab + by + kab = pos,方程實質是沒有改變的,我們在化簡一下，變成a(x- kb) + b (y + ka) = pos，使y變正，只需要加若干個a即可，具體數目可以算出來。
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
ll xx,yy;
ll gcd(ll a,ll b){
if(b == 0)
return a;
return gcd(b,a%b);
}
void extend_Eulid(ll a,ll b){
if(b == 0){
xx = 1;
yy = 0;
return;
}
else{
extend_Eulid(b,a%b);
int temp = xx;
xx = yy;
yy = temp - a/b * yy;
}
}
int main(){
//freopen("1.txt","r",stdin);
//freopen("3.txt","w",stdout);
ll posx,posy,vx,vy,L;
while(scanf("%lld%lld%lld%lld%lld",&posx,&posy,&vx,&vy,&L) != EOF){
ll dvx = vy - vx;
ll dpos = posx - posy;
ll gcdx = gcd(L,dvx);
if(dpos % gcdx){
printf("Impossible\n");
}
else{
dvx = dvx / gcdx;
dpos = dpos / gcdx;
L /= gcdx;
extend_Eulid(L,dvx);
yy *= dpos; www.2cto.com
xx *= dpos;
if(L < 0) L = -L;
if(yy > 0 && xx > 0) yy %= L;
else{
ll cnt = yy/L;
cnt = -cnt;
cnt++;
yy = (yy + L * cnt)%L;
}
printf("%lld\n",yy);
}
}
return 0;
}
作者：wmn_wmn
