Hide

Problem E
Hljóðstilling

/problems/iceland.hljodstilling/file/statement/en/img-0001.jpg
Image from flickr.com
Sara often listens to music when driving with friends. Here follows a transcript of one such car ride.
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
CPU Time limit 3 seconds
Memory limit 1024 MB
Languages English, Íslenska
Author
Arnar Bjarni Arnarson
Source Forritunarkeppni Framhaldsskólanna 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in