题目

https://www.luogu.com.cn/problem/P2737

思路

裴蜀定理：方程\(\sum_{i=1}^{n}k_ix_i=b\)有整数解当且仅当\(gcd(k_1,k_2,...,k_n)|b\)

不知道的同学可以做一下这题：【模板】裴蜀定理

证明：

必要性

设 \(gcd(k_1,k_2,...,k_n)=g\)（后面也用g表示），则 \(g|k1,g|k2....\)，又\(b=\sum_{i=1}^{n}k_ix_i\)，所以\(g|b\)。

充分性

先证方程\(\sum_{i=1}^{n}k_ix_i=g\)有解，当\(n=2\)时根据扩展欧几里得算法显然成立，利用数学归纳法，假设\(n=k\)时方程有解，那么\(n=k+1\)时：

\(k_1x_1+k_2x_2+....+k_nx_n+k_{n+1}x_{n+1}=gcd(k_{n+1},g)\)，就要证存在\(x_{n+1}\) 使 \(k_{n+1}x_{n+1}+\lambda g=gcd(k_{n+1},g)\)

解释一下\(\lambda g\)，这是说因为 \(k=n\) 时方程有解，所以我们将解中的每一个\(x\)变为原来的 \(\lambda\) 倍，就使得\(\sum_{i=1}^{n}k_ix_i=\lambda g\)，其中 \(\lambda\) 是任意整数。

那么，改写一下 \(k=n+1\)时的方程 ：\(ax+by=gcd(a,b)\)，肯定有解。

所以方程\(\sum_{i=1}^{n}k_ix_i=g\)有解，又因为\(g|b\)，所以我们将方程\(\sum_{i=1}^{n}k_ix_i=g\) 的解变为原来的\(\frac{b}{g}\)倍就可以了。

综上，裴蜀定理得证。

解决问题

分析一下，这道题就是要找一个最大的\(b\)，使得方程 \(\sum_{i=1}^{n}k_ix_i=b\) 无自然数解。

根据裴蜀定理，如果\(g>1\)，可以找到一个任意大的\(b\)（\(g\nmid b\)），使该方程没有整数解，自然更没有自然数解了，输出"0"。

如果\(g=1\)，方程一定存在整数解，且\(b\)足够大时，一定能通过解的调整使各个\(x\)都变为自然数，所以满足题意的 \(b\) 是有上界的。

我们关心的是这个上界是多少。我太弱了不会证，那就开个1e6的数组试试吧，接下来跑DP就完事了。

然后，过了。。。

代码

#include<cstdlib>
#include<algorithm>
using namespace std;
int dp[1000000],a[11];
int gcd(int x,int y){
    if(x<y) swap(x,y);
    if(!y) return x;
    return gcd(y,x%y);
}
int main(){
    int n,i,j,ans=0,g=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        g=gcd(g,a[i]);
    }
    dp[0]=1;
    for(i=1;i<=1000000;i++){
        for(j=1;j<=n;j++){
            if(i>=a[j])
                dp[i]|=dp[i-a[j]];
        }
        if(!dp[i]) ans=i;
    }
    if(g==1) printf("%d",ans);
    else printf("0");
    system("pause");
    return 0;
}

补充

如果想进一步看看上界的值怎么算的巨佬请移步rqy小姐姐的博客https://www.luogu.com.cn/blog/rqy/solution-p2737