APTX Blog

A Moe Blog Set By APTX

#C/C++#裴蜀定理(貝祖等式)

文章目录[隐藏]

裴蜀定理

在数论中,裴蜀等式是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a,b和m,关于未知数 x和y的线性丢番图方程(称为裴蜀等式):ax+by=m

有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解 x、y都称为裴蜀数,可用扩展欧几里得算法求得。

就是关于 x,  的不定方程 ax + by   有整数解的充要条件是 g 。

题目见洛谷:P4549

模板

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注