• 最大公约数

ll gcd(ll x, ll y) {
    while (y) {
        ll tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

• 最小公倍数

ll lcm(ll x, ll y) {
    return x * y / gcd(x, y);
}

• 分数化简

----分母除以最大公约数即为最简

y = y / gcd(x, y);

• gcd的几个公式

  • gcd(a, b) = gcd(a - b, b)
  • gcd(x^a−1, x^b−1)=xgcd(a,b)−1
  • gcd(Fib(a),Fib(b))=Fib(gcd(a,b))