求二元一次方程的一组整数解（exgcd 原理存档）

userId_undefined

cjdstttttt

时空双修者尊贵铂金题解仙人勇敢小狗CSP-J一等奖出题人

2025-04-20 15:13:48

发布于：广东

64阅读
0回复
0点赞

13x+32y=9713x+26y+6y=9713x+32y=97\\ 13x+26y+6y=97\\

令 x′=x+2yx'=x+2y，则

13x′+6y=97x′+12x′+6y=9713x'+6y=97\\ x'+12x'+6y=97

令 y′=2x′+yy'=2x'+y，则

x′+6y′=97x'+6y'=97\\

此时已化为最简。
不难发现一个符合题意的解为

{x′=97y′=0\begin{cases} x'=97\\y'=0 \end{cases}

则

y=y′−2x′=−194x=x′−2y=485y=y'-2x'=-194\\ x=x'-2y=485

∴\therefore 一组符合原方程的整数解为

{x=485y=−194\begin{cases} x=485\\y=-194 \end{cases}

userId_undefined
去预览
0/2000

全部评论 8

  • userId_undefined

    ppl 大帝

    传道者题解仙人CSP-J一等奖尊贵铂金出题人代码纠察员

    或许把常数替换为字母更具说服力

    2025-04-20 来自 浙江

    1
    • userId_undefined

      cjdstttttt

      回复ppl 大帝

      这样不好换元

      2025-04-20 来自 广东

      0
    • userId_undefined

      cjdstttttt

      回复ppl 大帝

      毕竟没有公式法

      2025-04-20 来自 广东

      0
    • userId_undefined

      ppl 大帝

      回复cjdstttttt

      可以用下取整，例如前几行可以这样写：

      ax+by=cax+by=c

      ax+(⌊ba⌋×a)y+(b−⌊ba⌋×a)y=cax+(⌊ \frac{b}{a}⌋ \times a)y + (b-⌊ \frac{b}{a}⌋ \times a)y=c

      令 x′=x+⌊ba⌋×ax′=x+⌊ \frac{b}{a}⌋ \times a，则

      ax′+(b−⌊ba⌋×a)y=cax′+(b-⌊ \frac{b}{a}⌋ \times a)y=c

      2025-04-20 来自 浙江

      1
  • userId_undefined

    ZmjjKK

    那个{是怎么打出来的，我不会

    2025-08-06 来自 上海

    0
    • userId_undefined

      cjdstttttt

      回复ZmjjKK

      {x=114514y=1919810\begin{equation*} \begin{cases} x=114514\\ y=1919810\\ \end{cases} \end{equation*} 

      $$
\begin{equation*}
\begin{cases}
x=114514\\
y=1919810\\
\end{cases}
\end{equation*}
$$

      2025-08-06 来自 浙江

      0
    • userId_undefined

      ZmjjKK

      回复cjdstttttt

      谢谢

      2025-08-06 来自 上海

      0
  • userId_undefined

    ppl 大帝

    传道者题解仙人CSP-J一等奖尊贵铂金出题人代码纠察员

    顶

    2025-04-20 来自 浙江

    0
  • userId_undefined

    cjdstttttt

    时空双修者尊贵铂金题解仙人勇敢小狗CSP-J一等奖出题人

    顶

    2025-04-20 来自 广东

    0
  • userId_undefined

    亚洲卷王 AK IOI

    %%%

    2025-04-20 来自 北京

    0
  • userId_undefined

    cjdstttttt

    时空双修者尊贵铂金题解仙人勇敢小狗CSP-J一等奖出题人

    ddd

    2025-04-20 来自 广东

    0
  • userId_undefined

    cjdstttttt

    时空双修者尊贵铂金题解仙人勇敢小狗CSP-J一等奖出题人

    顶

    2025-04-20 来自 广东

    0
  • userId_undefined

    cjdstttttt

    时空双修者尊贵铂金题解仙人勇敢小狗CSP-J一等奖出题人

    顶

    2025-04-19 来自 广东

    0

热门讨论