Problem E
Hljóðstilling
Languages
en
is
SARA: “Music right?”
HANNES: “Yeeea!”
ARNAR: “Hey Google! Play Despacito!”
Hannes corrects the volume quickly.
SARA: “HOW DARE YOU SET THE VOLUME TO ELEVEN?!?!?! 11 IS NOT DIVISIBLE BY ANY OF MY FAVOURITE NUMBERS!!!”
Sara despises it when the volume is set to a number not divisible by at least one of her favourite numbers. For example if her favourite numbers were $2$ and $5$ it’d be fine to set the volume to $15$, $18$ or $20$ but $11$, $17$ or $21$ would not be okay. To simplify the life of everyone involved, Sara’s favourite numbers are always prime.
It depends on the radio model what range of volumes are offered, but all volume settings are always integers. Given the interval that the radio supports and Sara’s favourite numbers, can you say how many volume settings are possible that she’d be alright with?
Input
Integers $L$ and $R$ where $1 \leq L \leq R \leq 10^{14}$, the interval that the radio supports, and in integer $k$ where $1 \leq k \leq 20$. Finally a single line with $k$ integers $a_1, a_2, \dotsc , a_k$, Sara’s favourite numbers. It will hold for all $i$ that $2 \leq a_i \leq 7\, 919$ and $a_i$ is prime.
Output
A single integer $n$, the number of volume settings that Sara is alright with on this radio.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$R-L \leq 10\, 000$ |
|
2 |
20 |
$k = 1$ |
|
3 |
15 |
$k \leq 2$ |
|
4 |
15 |
$k \leq 3$ |
|
5 |
30 |
No further constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
1 30 2 2 5 |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
17 100 1 7 |
12 |
