POJ 1061 Frog Dating

math poj extend_gcd gcd

貼一下之前做的題目. 題目解法就是extend gcd.
之前卡了好一陣子, 即使看了別人的做法也不明白.

上面已经列出找一个整数解的方法，在找到p*a+q*b = Gcd(a, b)的一组解p0,q0后，p*a+q*b = Gcd(a, b)的其他整数解满足：
p = p0 + b/Gcd(a, b)*t
q = q0 - a/Gcd(a, b)  t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p*a+q*b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可，但是所得解并不是该方程的所有解，找其所有解的方法如下：
在找到p*a+q*b = Gcd(a, b)的一组解p0,q0后，可以
得到p*a+q*b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p*a+q*b = c的其他整数解满足：
p = p1 + b/Gcd(a, b)*t
q = q1 - a/Gcd(a, b)*t(其中t为任意整数)
p 、q就是p*a+q*b = c的所有整数解。
當初想不到的重點baidu
poj1061.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include <cstdio>

typedef long long LL;

LL extend_gcd(LL a, LL &x, LL b, LL &y) {
  if(b == 0) {
    x = 1;
    y = 0;
    return a; //gcd(a, 0) == a
  } else {
    LL c = extend_gcd(b, x, a%b, y);
    int q = x;
    x = y;
    y = q - (a/b)*y;
    return c;
  }
}

int main() {
  LL x, y, xstep, ystep, L;
  while(scanf("%lld%lld%lld%lld%lld", &x, &y, &xstep, &ystep, &L) != EOF) {

    LL r, r1, r2;
    LL a = ystep - xstep, c;

    if(a > 0) {
      a = ystep - xstep;
      c = x - y;
    } else {
      a = xstep - ystep;
      c = y - x;
    }

    LL gcd = extend_gcd(a, r1, L, r2);

    if( c % gcd == 0) {
      r1 = r1*(c/gcd);
      r = L/gcd;

      printf("%lld\n", (r1%r + r)%r);
    } else {
      printf("Impossible\n");
    }
  }
  return 0;
}