P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解

· · 题解

P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解

为了红名疯狂写题解的蒟蒻又来啦~

题目传送门

前置知识

​在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 a、b 和它们的最大公约数 d = \gcd(a, b)，关于未知数 x 和 y 的线性丢番图方程

ax + by = m

有解当且仅当 d | m。裴蜀等式有解时必然有无穷多个整数解。

特别来说，方程 ax + by = 1 有解当且仅当整数 a 和 b 互素。

对于多个整数而言，情况是类似的。

思路

为方便，这里我们使用 \gcd(\{A_i\}) 表示 \{A_i\} 中所有数的最大公约数。

首先，一个显而易见的结论是：

当 \gcd(\{A_i\}) = 1 时，凑不出的数目只有有限多个；而当 \gcd(\{A_i\}) > 1 时，凑不出的数目有无限多个。

看到大佬们似乎都对这个结论一笔带过，这里蒟蒻就给出证明方式：

首先，由裴蜀定理可得，当 \gcd(\{A_i\}) = 1 时，对于任意 X \in \mathbb{N^+}，方程

A_1\alpha + A_2\beta + \cdots = X

都存在无穷多个整数解，那么必定只有有限多个 X，使得该方程无自然数解。

证毕。

判断出是否输出 INF 后，我们就可以使用 dp 的做法将剩余情况处理掉了。

dp 数组只用开 100005 的大小，对于本题的数据范围足够了。

注意到如果某个 k - A_i 能被凑出，k 也必能被凑出，因此状态转移方程为 dp_k = \max(dp_k,dp_{k - A_i})（注意写法！一定是 \max！否则有可能原本可以的数变得不行了，然后全 WA）。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int gcd(int m, int n)
{
    if(n)
    {
        return gcd(n, m % n);
    }
    else
    {
        return m;
    }
}//求gcd(m,n),常见的递归写法
const int MAXN = 105, MAX_DP = 100005;//又来定义
int n, a[MAXN], dp[MAX_DP], ans;
bool notCoprime(int *arr)//返回arr数组中所有数的最大公约数是否大于1
{
    int g = arr[0];
    for(int i = 1; i < n; i++)
    {
        g = gcd(g, arr[i]);
        if(g == 1)
        {
            return false;//如果g已经为1，不用再循环，直接返回
        }
    }
    return g > 1;
}//定义函数，运行更快
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }//输入
    if(notCoprime(a))//如果gcd({A_i})>1
    {
        printf("INF");
        return 0;//直接结束
    }
    dp[0] = 1;//注意0是被认为能被凑出的，否则所有数都凑不出来，循环检查时可以不用从0开始
    for(int i = 0; i < n; i++)
    {
        for(int j = a[i]; j < MAX_DP; j++)
        {
            dp[j] = max(dp[j], dp[j - a[i]]);//状态转移方程
        }
    }
    for(int i = 1; i < MAX_DP; i++)
    {
        if(!dp[i])
        {
            ans++;//如果dp[i]=0,多一个凑不出的数
        }
    }
    printf("%d", ans);//输出
    return 0;
}

AC 记录