P16284 [Lanqiao Cup 2026 NOI Qualifier Python A Group] Music Metronome

Xiaoming is learning music. He finds that playing different instruments requires matching different beats. Now there are $N$ kinds of instruments, and each instrument has its own “beat period” (in seconds). In music performance, if a certain moment is exactly an integer multiple of an instrument’s beat period, then this instrument will make a sound at that moment. For example, an instrument with a beat period of $3$ seconds will make a sound at the $3$rd second, the $6$th second, the $9$th second, and so on. Xiaoming wants to know: within the first $T$ seconds (i.e., from the $1$st second to the $T$th second, including the $T$th second), how many moments are there when exactly $K$ instruments make sounds at the same time?

The first line contains three integers $N, T, K$, representing the number of instruments, the observation duration, and the number of instruments that make sounds simultaneously. The second line contains $N$ integers $p_1, p_2, \dots, p_N$, representing the beat period of each instrument (unit: seconds).

Output one line with one integer, representing the number of moments when exactly $K$ instruments make sounds simultaneously.

### Sample Explanation 1 The instrument periods are $2$, $3$, and $4$ seconds. Within the first $12$ seconds, the sounding situation at each moment is shown in the table below: | Time | Instrument 1 (period 2) | Instrument 2 (period 3) | Instrument 3 (period 4) | Number of sounding instruments | |:----:|:------------------------:|:------------------------:|:------------------------:|:------------------------------:| | 1 | - | - | - | 0 | | 2 | ✓ | - | - | 1 | | 3 | - | ✓ | - | 1 | | 4 | ✓ | - | ✓ | 2 | | 5 | - | - | - | 0 | | 6 | ✓ | ✓ | - | 2 | | 7 | - | - | - | 0 | | 8 | ✓ | - | ✓ | 2 | | 9 | - | ✓ | - | 1 | | 10 | ✓ | - | - | 1 | | 11 | - | - | - | 0 | | 12 | ✓ | ✓ | ✓ | 3 | In the table, “✓” means the instrument makes a sound at that moment, and “-” means it does not. The moments when exactly $2$ instruments make sounds simultaneously are $t = 4, 6, 8$, for a total of $3$ moments. ### Sample Explanation 2 The instrument periods are $2$, $3$, $5$, and $6$ seconds. Within the first $20$ seconds, the moments when exactly $3$ instruments make sounds simultaneously are shown in the table below: | Time | Instrument 1 (period 2) | Instrument 2 (period 3) | Instrument 3 (period 5) | Instrument 4 (period 6) | Number of sounding instruments | |:----:|:------------------------:|:------------------------:|:------------------------:|:------------------------:|:------------------------------:| | 6 | ✓ | ✓ | - | ✓ | 3 | | 12 | ✓ | ✓ | - | ✓ | 3 | | 18 | ✓ | ✓ | - | ✓ | 3 | Explanation: the least common multiple of instruments $1$, $2$, and $4$ is $6$, so at times $6, 12, 18$ these three instruments will make sounds at the same time. Instrument $3$ (period $5$) does not make a sound at these times, so there are exactly $3$ instruments. ### Constraints and Notes for Test Cases For $30\%$ of the test cases, $N \leq 5$, $T \leq 100$. For $60\%$ of the test cases, $N \leq 10$, $T \leq 1000$. For all test cases, $1 \leq N \leq 20$, $1 \leq T \leq 10000$, $1 \leq K \leq N$, $1 \leq p_i \leq 100$. Translated by ChatGPT 5