简洁的取模还原分数方法

假设同余 p 下的数 q 原本是一个分子分母的绝对值都很小的分数（准确讲，是已知 |a|\le A, |b|\le B，且 AB = o(p)），我们可以还原出一组解 q\equiv 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);
}

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