Running-Turtle

My blogs

0%

Frobenius定理与P8646

发表于 分类于

Frobenius 定理

核心内容

对于两个正整数 $a$ 和 $b$ （假设 $\gcd(a, b) = 1$），考虑以下整数线性组合：

$$
S = {ax + by \mid x, y \geq 0},
$$

即使用 $a$ 和 $b$ 的非负整数线性组合能够表示的所有正整数。根据 Frobenius 定理，有以下结论：

  1. 能表示的最小正整数：如果 $\gcd(a, b) = 1$，则最小能表示的正整数为 $\min(a, b)$。

  2. 不能表示的最大正整数：形如 $ax + by$ 的线性组合不能表示的最大正整数为：

    $$
    N = ab - a - b.
    $$

  3. 不能表示的正整数个数：不能表示的正整数的总个数为：

    $$
    \frac{(a-1)(b-1)}{2}.
    $$

推广到多个变量

对于 $a_1, a_2, \ldots, a_k$，$k > 2$，若 $\gcd(a_1, a_2, \ldots, a_k) = 1$，仍然有：

  • $ax_1 + bx_2 + \cdots$ 表示的正整数集合是有限缺口的；

  • 但无法通过闭式公式直接确定所有不可表示的数。

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

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。比如一共有 $3$ 种蒸笼，分别能放 $3$ 、 $4$ 和 $5$ 个包子。当顾客想买 $11$ 个包子时，大叔就会选 $2$ 笼 $3$ 个的再加 $1$ 笼 $5$ 个的（也可能选出 $1$ 笼 $3$ 个的再加 $2$ 笼 $4$ 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 $3$ 种蒸笼，分别能放 $4$ 、 $5$ 和 $6$ 个包子。而顾客想买 $7$ 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

由裴蜀定理，可以得出，必须 $\gcd_{i=1}^nA_i=1$ 才能凑出所有数，不然只能凑出一些 $kg$ 的形式。

满足了 $g=1$ 之后，由 Fronebius 定理，我们知道这题不能构造的数是有限的，就是说 $A_1x_1+A_2x_2+\cdots$ 表示的正整数是有限缺口的。

考虑用完全背包求一下能表示哪些数，一共有 $\max=100$ 个数据，我们将第二维尽量放大，精准需要多大很难用数学推导出来，1 S 的时限内，可以将第二维放宽到 $10^6$ ，可以通过题目。

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
void solve(){
    int n, g = 0;
    cin >> n;

    vector<int> f(1E6), a(n);
    for(auto &x : a) {
        cin >> x;
        g = __gcd(g, x);
    }

    if(g != 1) {
        cout << "INF\n";
        exit(0);
    }

    f[0] = 1;
    for(auto &x : a) { // 100
        for(int j = 0; j <= 1E6; j ++) {
            if(f[j] && j + x <= (int)1E6) f[j + x] = 1;
        }
    }

    int res = 0;
    for(int i = 0; i <= 1E6; i ++) {
        res += !f[i];
    }
    cout << res << '\n';
}