算法介绍 给定一个长度为
n n n 的整数序列
A A A 和一个待定整数序列
X X X ，求
S = ∑ i = 1 n A i × X i S = \sum \limits_{i = 1}^{n} A_i \times X_i S = i = 1 ∑ n A i × X i 在正数范围内的最小值。
看上去似乎有点无从下手。
那先从简单的开始！我们来考虑
n = 2 n = 2 n = 2 的情况，此时问题简化为求
A 1 X 1 + A 2 X 2 A_1 X_1 + A_2 X_2 A 1 X 1 + A 2 X 2 的最小值。
如果我们设
a , b a, b a , b 是不全为
0 0 0 的整数，那么有
裴蜀定理 （Bézout's Lemma）：
对于任意整数 x , y x, y x , y gcd ( a , b ) ∣ ( a x + b y ) \gcd (a, b) \mid (ax + by) g cd( a , b ) ∣ ( a x + b y )
存在整数 x , y x, y x , y a x + b y = gcd ( a , b ) ax + by = \gcd (a, b) a x + b y = g cd( a , b )
因此，
a x + b y ax + by a x + b y 的最小正整数值显然是
gcd ( a , b ) \gcd (a, b) g cd( a , b ) 。上述问题的答案就是
gcd ( A 1 , A 2 ) \gcd(A_1, A_2) g cd( A 1 , A 2 ) 。
那么，当
n ≥ 3 n \ge 3 n ≥ 3 呢？我们尝试推广裴蜀定理。
假设有三个整数
a , b , c a, b, c a , b , c 。我们首先对前两个数应用裴蜀定理，存在整数
x 1 , x 2 x_1, x_2 x 1 , x 2 ，使得
a x 1 + b x 2 = gcd ( a , b ) ax_1 + bx_2 = \gcd (a, b) a x 1 + b x 2 = g cd( a , b ) 。接下来，将这个结果与第三个数
c c c 结合，即存在整数
k , x 3 k, x_3 k , x 3 ，使得
gcd ( a , b ) × k + c x 3 = gcd ( gcd ( a , b ) , c ) \gcd (a, b) \times k + cx_3 = \gcd( \gcd(a, b), c) g cd( a , b ) × k + c x 3 = g cd( g cd( a , b ) , c ) 。
我们知道，最大公约数有性质：
gcd ( a , b , c ) = gcd ( gcd ( a , b ) , c ) \gcd (a, b, c) = \gcd (\gcd(a, b), c) g cd( a , b , c ) = g cd( g cd( a , b ) , c ) ，因此存在整数组合使得
a x 1 + b x 2 + c x 3 = gcd ( a , b , c ) ax_1 + bx_2 + cx_3 = \gcd(a, b, c) a x 1 + b x 2 + c x 3 = g cd( a , b , c ) ，且不存在更小的正数解。
这样推广下去，最终无论
n n n 的大小，问题的最小正数解都是所有
A i A_i A i 的最大公约数的绝对值。因此，我们只需要计算整个序列
A A A 的最大公约数，并取其绝对值即可。
正确性证明 我们设
a , b a, b a , b 是不全为
0 0 0 的整数，那么一定有
gcd ( a , b ) ∣ a \gcd(a, b) \mid a g cd( a , b ) ∣ a 且
gcd ( a , b ) ∣ b \gcd(a, b) \mid b g cd( a , b ) ∣ b 。设
x , y x, y x , y 为整数，则有
gcd ( a , b ) ∣ a x \gcd(a, b) \mid ax g cd( a , b ) ∣ a x 且
gcd ( a , b ) ∣ b y \gcd(a, b) \mid by g cd( a , b ) ∣ b y ，因此
gcd ( a , b ) ∣ ( a x + b y ) \gcd(a, b) \mid (ax + by) g cd( a , b ) ∣ ( a x + b y ) 。
对于定理的第二点，若
a a a 和
b b b 任意一个等于
0 0 0 ，则
gcd ( a , b ) \gcd(a, b) g cd( a , b ) 的值为非零数的值，此时定理显然成立。
若
a b ≠ 0 ab \neq 0 ab = 0 ，由于
gcd ( a , b ) = gcd ( a , − b ) \gcd(a, b) = \gcd(a, -b) g cd( a , b ) = g cd( a , − b ) ，我们不妨设
a , b a, b a , b 都大于
0 0 0 ，
a ≥ b a \ge b a ≥ b ，且有
gcd ( a , b ) = d \gcd(a, b) = d g cd( a , b ) = d 。
对
a x + b y = d ax + by = d a x + b y = d ，两边同时除以
d d d ，得到
a 1 x + b 1 y = 1 a_1x + b_1y = 1 a 1 x + b 1 y = 1 ，其中
a 1 , b 1 a_1, b_1 a 1 , b 1 互质。接下来证明
a 1 x + b 1 y = 1 a_1x + b_1y = 1 a 1 x + b 1 y = 1 。
我们先来回顾一下辗转相除法：
gcd ( a , b ) → gcd ( b , a m o d b ) → ⋯ \gcd(a, b) \rightarrow \gcd(b, a \bmod b) \rightarrow \cdots g cd( a , b ) → g cd( b , a mod b ) → ⋯ 。我们把模出来的数记作
r r r ，则有：
gcd ( a 1 , b 1 ) = gcd ( b 1 , r 1 ) = gcd ( r 1 , r 2 ) = ⋯ = gcd ( r n − 1 , r n ) = 1 \gcd(a_1, b_1) = \gcd(b_1, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_{n - 1}, r_n) = 1 g cd( a 1 , b 1 ) = g cd( b 1 , r 1 ) = g cd( r 1 , r 2 ) = ⋯ = g cd( r n − 1 , r n ) = 1 把辗转相除法中的运算展开成带余除法，得到：
a 1 = q 1 b 1 + r 1 ( 0 ≤ r 1 < b 1 ) b 1 = q 2 r 1 + r 2 ( 0 ≤ r 2 < r 1 ) r 1 = q 3 r 2 + r 3 ( 0 ≤ r 3 < r 2 ) ⋯ r n − 3 = q n − 1 r n − 2 + r n − 1 r n − 2 = q n r n − 1 + r n r n − 1 = q n + 1 r n \begin{align*}
a_1 & = q_1b_1 + r_1 & (0 \le r_1 < b_1) \\
b_1 & = q_2r_1 + r_2 & (0 \le r_2 < r_1) \\
r_1 & = q_3r_2 + r_3 & (0 \le r_3 < r_2) \\
& \cdots & \\
r_{n - 3} & = q_{n - 1}r_{n - 2} + r_{n - 1} & \\
r_{n - 2} & = q_nr_{n - 1} + r_n & \\
r_{n - 1} & = q_{n + 1}r_n
\end{align*} a 1 b 1 r 1 r n − 3 r n − 2 r n − 1 = q 1 b 1 + r 1 = q 2 r 1 + r 2 = q 3 r 2 + r 3 ⋯ = q n − 1 r n − 2 + r n − 1 = q n r n − 1 + r n = q n + 1 r n ( 0 ≤ r 1 < b 1 ) ( 0 ≤ r 2 < r 1 ) ( 0 ≤ r 3 < r 2 ) 我们令辗转相除法在除到互质的时候退出，则
r n = 1 r_n = 1 r n = 1 ，所以有：
r n − 2 = q n r n − 1 + 1 r_{n - 2} = q_nr_{n - 1} + 1 r n − 2 = q n r n − 1 + 1 即：
1 = r n − 2 − q n r n − 1 1 = r_{n - 2} - q_nr_{n - 1} 1 = r n − 2 − q n r n − 1 用倒数第三个式子
r n − 1 = r n − 3 − q n − 1 r n − 2 r_{n - 1} = r_{n - 3} - q_{n - 1}r_{n - 2} r n − 1 = r n − 3 − q n − 1 r n − 2 代入上式，得：
1 = ( 1 + q n q n − 1 ) r n − 2 − q n r n − 3 1 = (1 + q_nq_{n - 1}) r_{n - 2} - q_nr_{n - 3} 1 = ( 1 + q n q n − 1 ) r n − 2 − q n r n − 3 然后用同样的办法逐个地消去
r n − 2 , ⋯ , r 1 r_{n - 2}, \cdots, r_1 r n − 2 , ⋯ , r 1 ，即可证得
1 = a 1 x + b 1 y 1 = a_1x + b_1y 1 = a 1 x + b 1 y 。
代码实现 CPP #include <iostream>
#include <algorithm>
using namespace std;
int n, a, ans;
int main () tie (nullptr );
ios::sync_with_stdio (false );
cin >> n >> a;
ans = a;
for (int i = 2 ; i <= n; ++i)
cin >> a, ans = __gcd(ans, abs (a));
cout << ans << '\n' ;
return 0 ;
}
P4549 【模板】裴蜀定理