发布时间：2025-05-22

裴蜀定理

$ax+by=n$有解当且仅当$\gcd(a,b)|n$

可以拓展到多个整数

$exgcd(a,b,x,y)$求出特殊解，$dx=\frac{b}{g},dy=\frac{a}{g}$

有通解如下：

$$\begin{cases} x=x+t\cdot dx \\ y=y-t \cdot dy \end{cases}$$

进一步结论：

$ax+by=n,a,b$互素，记$C=ab-a-b$(必定为奇数)

则对任意的整数$n \in[0,C]$,$n$和$C-n$只有一个能被表示

例子：$a,b$两种不同的面值，不能表示的最大钱数为$C$

几何意义：

这条直线与第一象限相交组成三角形$(0,0),(0,a),(b,0)$，$n$小于$ab$时直线只会有一个整数点，随着向右上方移动，直至有至少两个整数点

当$n \lt ab$时，小于等于$n$的能被表示的非负整数数量为$\sum_{i=0}^{\frac{n}{a}}\frac{n-ia}{b}$，可以用类欧几里得求解