【题解】Optimal Currency Exchange

一道很有意思的数学题,第一眼没觉得有多难,结果瞎搞了一个多小时才AC,真是有趣……

【题解】青蛙的约会

exgcd大水题……

模线性方程组与中国剩余定理

这篇文章会比较杂乱,因为好多内容都被我搞到一块来了…先写一个内容摘要可供参考:

  1. 利用扩展欧几里得算法(exgcd)求解二元一次不定方程
  2. 利用exgcd求解单变元模线性方程
  3. 利用中国剩余定理(CRT)与扩展中国剩余定理(exCRT)求解单变元模线性方程组
    ……

欧几里得与扩展欧几里得定理

$$ \gcd(a,b) = \gcd (b,a \text{ mod } b) $$

$$ \begin{cases} ax_1 + by_1 = \gcd(a,b) \newline bx_2 + (a\text{ mod }b)y_2 = \gcd(b,a\text{ mod }b) \end{cases} \Rightarrow \begin{cases} x_1 = y_2 \newline y_1 = x_2- \lfloor\dfrac{a}{b}\rfloor \times y_2 \end{cases}$$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×