正題

題目鏈接:https://www.luogu.org/problem/P4549

---

題目大意

一個整數序列$A$，一個整數序列$X$使得
$$\sum _{i=1}^n{A}_i{X}_i=S$$
求$S$可能的最小正整數值。

---

裴蜀定理

對于方程$$ax+by=S(x,y\in {\mathbb{N}}^{+})$$
的充要條件是$gcd(a,b)\mid S$

證明$:$
因為$gcd(a,b)\mid a$且$gcd(a,b)\mid b$。又因為有$x,y\in {\mathbb{N}}^{+}$
所以有$gcd(a,b)\mid ax$且$gcd(a,b)\mid by$也就是$gcd(a,b)\mid (ax+by)$
那么設$S=gcd(a,b)?k$那么有$S\mid (ax+by)?k?S\mid (axk+byk)$

---

解題思路

首先我們考慮這個序列并不是正整數但是我們可以讓$X_i$取反來達到所有都變成正整數的目的。

所以答案就是$$gcd(|A_1|,|A_2|,|A_3|,...,|A_n|)$$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,ans; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);ans=__gcd(ans,abs(x)); }printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P4549-[模板]裴蜀定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。