洛谷P4549 裴蜀定理模板

裴蜀定理：

若给出参数$a,b,c$，不定方程$ax+by=c$有解的充要条件是
$$gcd(a,b)|c$$

证明：

$gcd(a,b)$显然是$ax$的一个因子，也是$by$的一个因子，所以$ax+by$的含义为$gcd(a,b)$的两个倍数相加，结果一定还是$gcd(a,b)$的倍数，所以只需要$gcd(a,b)|c$，方程就有解

同样的原理，可以扩展至任意个数的参数：

给出$n$个参数$a_i$与$c$，使方程
$$\sum _{i=1}^n{a}_i{x}_i=c$$
有解的充要条件是
$$gcd(a_1,a_2,...,a_n)|c$$

例题：洛谷$P4549$

题意：

给出$n$个参数$a_i$，求另一个整数序列$x_i$，使得
$$S=\sum _{i=1}^n{a}_i{x}_i$$
满足$S>0$，且$S$最小

Solution：

显然右式是一个不定方程，那么$S$要存在取值就只可能是$gcd(a_1,a_2,...,a_n)$，这个就是答案了。不过$a_i$可能是负的，只需要取负$a_i$在计算就可以保证是正的了

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
using ull=unsigned long long;
const int N=2e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+9;

int main()
{
    #ifdef stdjudge
        freopen("in.txt","r",stdin);
    #endif
    int ans,n; cin>>n>>ans;
    if(ans<0) ans=-ans;
    while(--n)
    {
        int x; cin>>x;
        if(x<0) x=-x;
        ans=__gcd(ans,x);
    }     
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32