P16284 [蓝桥杯 2026 省 Python A 组] 音乐节拍器

Link: https://www.luogu.com.cn/problem/P16284

题目描述

小明在学习音乐，他发现不同乐器的演奏需要配合不同的节拍。现在有 $N$ 种乐器，每种乐器都有自己的“节拍周期”（以秒为单位）。

在音乐演奏中，如果某一时刻恰好是某个乐器节拍周期的整数倍，那么这个乐器就会在这一时刻发声。例如，一个节拍周期为 $3$ 秒的乐器会在第 $3$ 秒、第 $6$ 秒、第 $9$ 秒等时刻发声。

小明想知道：在前 $T$ 秒内（即第 $1$ 秒至第 $T$ 秒，包含第 $T$ 秒），恰好有 $K$ 种乐器同时发声的时刻有多少个？

输入格式

第一行包含三个整数 $N,T,K$，分别表示乐器数量、观察的时长、同时发声的乐器数量。

第二行包含 $N$ 个整数 $p_1,p_2,\dots ,p_N$，表示每种乐器的节拍周期（单位：秒）。

输出格式

一行，输出一个整数，表示恰好有 $K$ 种乐器同时发声的时刻数量。

输入输出样例 #1

输入 #1

3 12 2
2 3 4

输出 #1

3

输入输出样例 #2

输入 #2

4 20 3
2 3 5 6

输出 #2

3

输入输出样例 #3

输入 #3

5 100 1
7 11 13 17 19

输出 #3

36

说明/提示

【样例说明 1】

乐器周期分别为 $2$、$3$、$4$ 秒。在前 $12$ 秒内，每个时刻发声情况如下表所示：

时刻	乐器 1（周期 2）	乐器 2（周期 3）	乐器 3（周期 4）	发声乐器数
1	-	-	-	0
2	✓	-	-	1
3	-	✓	-	1
4	✓	-	✓	2
5	-	-	-	0
6	✓	✓	-	2
7	-	-	-	0
8	✓	-	✓	2
9	-	✓	-	1
10	✓	-	-	1
11	-	-	-	0
12	✓	✓	✓	3

表中“✓”表示该乐器在该时刻发声，“-”表示不发声。

恰好 $2$ 种乐器同时发声的时刻有：$t=4,6,8$，共 $3$ 个。

【样例说明 2】

乐器周期分别为 $2$、$3$、$5$、$6$ 秒。在前 $20$ 秒内，恰好 $3$ 种乐器同时发声的时刻如下表所示：

时刻	乐器 1（周期 2）	乐器 2（周期 3）	乐器 3（周期 5）	乐器 4（周期 6）	发声乐器数
6	✓	✓	-	✓	3
12	✓	✓	-	✓	3
18	✓	✓	-	✓	3

说明：乐器 $1$、$2$、$4$ 的最小公倍数为 $6$，所以在时刻 $6,12,18$ 这三个乐器会同时发声。乐器 $3$（周期 $5$）在这些时刻不发声，因此恰好 $3$ 种乐器。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$N\le 5$，$T\le 100$；

对于 $60\%$ 的评测用例，$N\le 10$，$T\le 1000$；

对于所有评测用例，$1\le N\le 20$，$1\le T\le 10000$，$1\le K\le N$，$1\le p_i\le 100$。

---

Solution

1. 题意

已知每种乐器的发声间隔，求一段时间 $1\sim T$ 内恰好有 $K$ 种乐器发声的次数。

2. 分析

非常基础的模拟问题。

对于每一个 $1\sim T$ 的时刻 $t$，依次用每一个 $p_i$ 判断当前的 $t$ 能否被其整除，累加得到这个时刻同时发声的乐器数量，判断是否等于 $K$ 即可。

重复 $T$ 次就得到了 $1\sim T$ 期间，同时演奏的乐器数恰好等于 $K$ 的次数。

总体的时间复杂度是 $O(NT)$。

3. 代码

using System;

class P16284
{
    static void Main()
    {
        var input = Console.ReadLine()?.Split();
        if (input == null || input.Length < 3) return;

        int N = Convert.ToInt32(input[0]);
        int T = Convert.ToInt32(input[1]);
        int K = Convert.ToInt32(input[2]);

        var pInput = Console.ReadLine()?.Split();

        int[] p = new int[N];
        for (int i = 0; i < N; i++)
        {
            p[i] = Convert.ToInt32(pInput[i]);
        }

        int ans = 0;
        for (int t = 1; t <= T; t++)
        {
            int cnt = 0;
            for (int i = 0; i < N; i++)
            {
                if (t % p[i] == 0)
                {
                    cnt++;
                }
            }
            if (cnt == K)
            {
                ans++;
            }
        }

        Console.WriteLine(ans);
    }
}

闲话

输入的都是整数，意味着所有的声音都要间隔至少 1 秒才能触发，也就意味着本题的“音乐”的 BPM 最大只有 60。