poj 1061 青蛙的约会 ——扩展欧几里得

March 18, 2013
POJ Math


#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define LL long long int
LL exgcd(LL a, LL b, LL &x, LL &y){
  if (b == 0){
    x = 1; y = 0; return a;
  }
  LL r = exgcd(b, a%b, x, y);
  LL t = x; x = y; y = t - a / b * y;
  return r;
}
LL gcd(LL a, LL b){
  return b ==0?a:gcd(b,a%b);
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1061.in", "r", stdin);
#endif
  LL x, y, m, n, L;
  while (~scanf("%lld%lld%lld%lld%lld", &x,&y,&m,&n,&L)){
    LL a = n - m, b = L, c = x - y;
    LL t, k;
    LL temp = gcd(a, b);
    if (c % temp != 0) {
      printf("Impossible\n"); continue;
    }
    a/=temp; b/=temp; c/=temp;
    exgcd(a,b,t,k);
    t *= c;
    LL kk = t/b;
    t = t-kk*b;
    if (t<0) t+=b;
    printf("%lld\n", t);
  }
  return 0;
}

学习了一下扩展欧几里德，注意，最后求最小正整数解的时候的处理方法，要判断ｔ是不是小于0,如果小于0就再加上ｂ。总结一下应用扩展欧几里德的方法： a * x + b * y = c; 求出d = gcd(a, b)，然后再化简一下原来的方程a /= d; b /= d; c /= d; 然后利用 a * x + b * y = 1求出一个解，x0, y0;然后得到了原方程的一个特解: x0 *= d; y0 *= d; 根据方程通解的公式：x = x0 + b * t; y = y0 - a * t; 求出最小的一个x的整数解。方法就是先假设x0 + b * t = 0; 令t1 = x0 / b; x0 = x0 - b * t1 如果x0小于0,那么x0 += b;否则解就是x0本身。今天又把这道题目做了一遍，重新学习了一下扩展欧几里德，理解比以前深了一点儿…… 上面的代码估计当时是抄的别人的。。这回自己写，但还是遇到了点儿问题，关键还是有一个细节理解错了，没有真正搞明白。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;

void exgcd(LL a, LL b, LL &d, LL &x, LL &y){
  if (!b){x = 1; y = 0; d = a; return;}
  LL t; exgcd(b, a%b, d, x, y);
  t = x; x = y; y = t - a / b * y;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1061.in", "r", stdin);
#endif
  LL x, y, m, n, L, d;
  scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L);
  LL B = n - m, X, Y, A = x - y;
  exgcd(B, L, d, X, Y);
  if (A%d != 0 || m == n) {
    printf("Impossible\n"); return 0;
  }
  LL s = L / d;
  X = X * A / d; X = (X%s + s) % s;
  printf("%lld\n", X);

  return 0;
}

注意34行，因为扩展欧几里得求出的一个解X不是最小解，但是属于一个模s的剩余系，所以要进行35行的处理。当初就是这里没有搞清楚。明显赶脚这次写的过程中比以前好多了，~↖(^ω^)↗ 　　唉，以前写的太挫了……今天复习了一下扩展欧几里德，重写了一遍。感觉比以前写的更精简了，理解更深入了一点。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

void exgcd(LL a, LL b, LL &d, LL &x, LL &y){
  if (!b){
     x = 1; y = 0; d = a; return;
  }
  else{
    exgcd(b, a % b, d, x, y);
    LL tem = x; x = y; y = tem - (a / b) * y;
  }
}

int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1061.in", "r", stdin);
#endif
  LL x1, y1, m, n, l, a, b, c, d, x, y;
  cin >> x1 >> y1 >> m >> n >> l;
  a = n - m; b = l; c = x1 - y1;
  exgcd(a, b, d, x, y);
  if (m == n || c % d){
    cout << "Impossible\n"; return 0;
  }
  x *= c / d;
  x = (x % l + l) % l;
  cout << x << endl;

  return 0;
}

　　注意理解第45行。　　思路：　　　　(mt + x) 同余于 (nt + y) 模 L 。所以可以得到方程：(n - m) * t + L * k = x - y; 用 exgcd求解，得到一个 (n - m) * t + L * k = gcd(n - m, L) 的一个解x，然后，x *= (x-y) / gcd(n - m, L) 得到的 x 就是原方程的一个解，但是要求最小的正整数 t ，由于原方程有 gcd(n-m, L) 个模 L 不同余的解，并且这些解同属于模 L 的剩余系，所以 x = (x % L + L ) % L ；就得到最小的解。　　感觉以前写的太挫了……

Read more