[CCC 2022 S1] Good Fours and Good Fives

题意

给出一个正整数 n。

要求统计有多少组非负整数解 (a,b) 满足：

4a + 5b = n

这里 a 表示用了多少个 4，b 表示用了多少个 5，并且不区分顺序。

思路

最直接的办法是枚举用了多少个 5。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：直接枚举 5 的个数，作为教学版朴素解和对拍基准。

long long n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    long long ans = 0;

    // 朴素做法：直接枚举用了多少个 5。
    // 如果剩下的部分可以被 4 正好填满，就是一种方案。
    for (long long cnt_five = 0; cnt_five * 5 <= n; cnt_five++) {
        long long rest = n - cnt_five * 5;
        if (rest % 4 == 0) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

如果当前用了 b 个 5，那么剩下的值就是 n - 5b。只要这个剩余值是非负数，并且能被 4 整除，就得到一种合法方案。

这份朴素代码的瓶颈是要把 b = 0..floor(n/5) 全部试一遍。

继续观察整除条件：

n - 5b ≡ 0 (mod 4)

因为 5 ≡ 1 (mod 4)，上式等价于：

b ≡ n (mod 4)

也就是说，合法的 b 不是随便出现的，而是：

n % 4, n % 4 + 4, n % 4 + 8, ...

只要这些值不超过 floor(n/5) 就行。

于是可以直接计数：

设 max_five = floor(n/5)；
设 first_five = n % 4，它是最小的合法 b；
如果 first_five > max_five，说明一个合法值都没有，答案是 0；
否则答案就是等差数列项数：

(max_five - first_five) / 4 + 1

这就把逐个枚举变成了 $O(1)$ 计算。

核心公式

题目要求统计非负整数解：

4a+5b=n

枚举 $b$ 时，合法条件为：

n-5b\equiv 0\pmod 4

因为 $5\equiv 1\pmod 4$ ，所以：

b\equiv n\pmod 4

令 $maxFive=\lfloor n/5\rfloor$ ， $first=n\bmod 4$ 。若 $first>maxFive$ ，答案为 $0$ ；否则：

ans=\left\lfloor\frac{maxFive-first}{4}\right\rfloor+1

公式解释：决定用了多少个 5 后，剩下部分必须全部由 4 组成。模 4 后能直接筛出所有合法的 b，它们按公差 4 出现，所以答案就是这个等差序列在合法范围内的项数。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

long long n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // 设用了 b 个 5，那么剩下的部分必须全部由 4 组成。
    // 条件是 n - 5 * b >= 0 且能被 4 整除。
    long long max_five = n / 5;

    // 因为 5 ≡ 1 (mod 4)，所以 5 * b ≡ b (mod 4)。
    // 要让 n - 5 * b 被 4 整除，就等价于 b ≡ n (mod 4)。
    long long first_five = n % 4;

    long long ans = 0;
    if (first_five <= max_five) {
        // 合法的 b 形成一个公差为 4 的等差数列：
        // first_five, first_five + 4, first_five + 8, ...
        ans = (max_five - first_five) / 4 + 1;
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(1)$
空间复杂度： $O(1)$

总结

这题本质是在统计方程 4a + 5b = n 的非负整数解个数。

关键一步是把“剩余部分能否由 4 组成”转成同余条件 b ≡ n (mod 4)，然后直接数出区间里有多少个这样的 b。

[CCC 2022 S1] Good Fours and Good Fives

目录

题意

思路

核心公式

代码

复杂度

总结