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

小明在学习音乐，他发现不同乐器的演奏需要配合不同的节拍。现在有 $N$ 种乐器，每种乐器都有自己的“节拍周期”（以秒为单位）。 在音乐演奏中，如果某一时刻恰好是某个乐器节拍周期的整数倍，那么这个乐器就会在这一时刻发声。例如，一个节拍周期为 $3$ 秒的乐器会在第 $3$ 秒、第 $6$ 秒、第 $9$ 秒等时刻发声。 小明想知道：在前 $T$ 秒内（即第 $1$ 秒至第 $T$ 秒，包含第 $T$ 秒），恰好有 $K$ 种乐器同时发声的时刻有多少个？

第一行包含三个整数 $N, T, K$，分别表示乐器数量、观察的时长、同时发声的乐器数量。 第二行包含 $N$ 个整数 $p_1, p_2, \dots, p_N$，表示每种乐器的节拍周期（单位：秒）。

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

### 【样例说明 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 \leq 5$，$T \leq 100$； 对于 $60\%$ 的评测用例，$N \leq 10$，$T \leq 1000$； 对于所有评测用例，$1 \leq N \leq 20$，$1 \leq T \leq 10000$，$1 \leq K \leq N$，$1 \leq p_i \leq 100$。