假设同余 p p p 下的数 q q q 原本是一个分子分母的绝对值都很小的分数（准确讲，是已知 ∣ a ∣ ≤ A , ∣ b ∣ ≤ B |a|\le A, |b|\le B ∣a∣≤A,∣b∣≤B，且 A B = o ( p ) AB = o(p) AB=o(p)），我们可以还原出一组解 q ≡ a / b q\equiv a/b q≡a/b。

万能欧几里得当然是可以做的。但是为什么说我们有一个异常简洁的方法呢？

pair<int, int> approx(int p, int q, int A) {
  int x = q, y = p, a = 1, b = 0;
  while (x > A) {
    swap(x, y); swap(a, b);
    a -= x / y * b;
    x %= y;
  }
  return make_pair(x, a);
}

相信这个东西可以成为大家调试时的有力工具。