1. 全栈程序员必看首页

【数学 裴蜀定理】luogu_4549 裴蜀定理

全栈程序员-站长 • • 未分类 • 阅读 2

【数学 裴蜀定理】luogu_4549 裴蜀定理题意给出 nnn 个数 AAA 求一组整数 XXX 使 X1A1 XnAnX 1A 1 X nA nX1 A1 Xn An 最小 求这个最小值 思路裴蜀定理 关于不定方程 ax by cax by cax by c 有整数解的充要条件是 gcd a b cgcd a b cgcd a b c 对于多个数 我们可以发现 ccc 的值为 那么

题意

给出 n n n个数 A A A，求一组整数 X X X，使 X 1 A 1 + . . . X n A n X_1A_1+…X_nA_n X1​A1​+...Xn​An​最小，求这个最小值。

思路

对于多个数，我们可以发现 c c c的值为 ( a , b ) (a,b) (a,b)的倍数，那么可以看做是 a a a，然后和下一个数计算。所以答案就是它们的 g c d gcd gcd了。

代码

#include 
     #include 
     int n, ans; int main() { 
    scanf("%d", &n); for (int i = 1, a; i <= n; i++) { 
    scanf("%d", &a); a = a < 0 ? -a : a; ans = std::__gcd(ans, a); } printf("%d", ans); }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/225771.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 上午8:34
下一篇 2026年3月17日 上午8:35


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号