数论
#C/C++#裴蜀定理(贝祖等式)
裴蜀定理 在数论中,裴蜀等式是一个关于最大公约数(或最大公约式)的定理.裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a,b和m,关于未知数 x和y的线性丢番图方程(称为裴蜀等式):ax+by=m 有整数解时当且仅当m是 a及b的最大公约数d的倍数.裴蜀等式有解时必然有无穷多个整数解,每组解 x,y都称为裴蜀数,可用扩展欧几里得算法求得. 就是关于 x, y 的不定方程 ax + by =c 有整数解的充要条件是 gcd(a,b)∣c . 题目见洛谷:P4549 模板 #include <cstdi...
2018年8月8日 0条评论 3544点热度 2人点赞 神楽坂 み