【模板】裴蜀定理

题目

洛谷P4549 裴蜀定理

题解

若a*x+b*y=c,当且仅当gcd(a,b)|c时有解,可推广到多个变量。

若A1*X1+A2*X2+A3*X3+……+An*Xn=S,当且仅当gcd(A1,A2,A3,……,An)|S时有解。

特别值得注意的是:gcd(0,a)=gcd(a,0)=|a|,gcd(-|a|,b)=gcd(|a|,b),在运算过程中,负数可以直接转成正数。

题中要求最小的S,即求gcd。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月25日 下午9:16

火钳刘明