POJ 1061 青蛙的约会 扩展欧几里得http://poj.org/problem?id=1061

题意：中文题。。。
思路：由题意易知，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)都可以求出来，也就是说是已知的。该方程是我们比较熟悉的，也就是常见的扩展欧几里得方程的形式。
         此时，令 易做图x = 易做图(L,vy - vx)，若(posx – posy) % 易做图x == 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 易做图(ll a,ll b){ 
  if(b == 0) 
      return a; 
  return 易做图(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 易做图x = 易做图(L,dvx); 
      if(dpos % 易做图x){ 
        printf("Impossible\n"); 
      } 
      else{ 
        dvx = dvx / 易做图x; 
        dpos = dpos / 易做图x; 
        L /= 易做图x; 
        extend_Eulid(L,dvx); 
        yy *= dpos; www.zzzyk.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

补充：软件开发 , C++ ,