Problem E
Hljóðstilling
Languages
en
is
SARA: “Tónlist eða?”
HANNES: “Ehaggi!”
ARNAR: “Hey Google! Play Despacito!”
Hannes stillir hljóðið í fljótu bragði.
SARA: “HVERNIG DIRFISTU AÐ STILLA HLJÓÐIÐ Á 11?!?!? 11 ER EKKI DEILANLEG MEÐ NEINUM AF UPPÁHALDSTÖLUNUM MÍNUM!!!”
Söru finnst nefnilega alveg ómögulegt þegar hljóðstillingin á hljómtækinu er ekki deilanleg með allavega einni af uppáhaldstölunum sínum. Til dæmis ef uppáhalds tölurnar hennar Söru væru $2$ og $5$ þá væri leyfilegt að stilla hljóðið á $15$, $18$ eða $20$ en $11$, $17$ eða $21$ væru ekki leyfileg gildi. Til að einfalda líf allra þá geta einungis frumtölur verið í uppáhaldi hjá Söru.
Það er mismunandi eftir hljómtækjum á hvaða bili er hægt að stilla hljóðið, en hljómtæki styðja einungis heiltölur. Gefið bilið sem hljómtækið styður og uppáhalds tölurnar hennar Söru geturðu sagt hvað eru margar hljóðstillingar í boði sem hún væri sátt með?
Inntak
Heiltölur $L$ og $R$, þar sem $1 \leq L \leq R \leq 10^{14}$, bilið sem hljómtækið styður og heiltölu $k$, þar sem $1 \leq k \leq 20$. Að lokum kemur ein lína með $k$ heiltölum $a_1, a_2, \dotsc , a_k$, uppáhalds tölur Söru. Það gildir fyrir öll $i$ að $2 \leq a_i \leq 7\, 919$ og $a_i$ er frumtala.
Úttak
Ein heiltala $n$, fjöldi hljóðstillinga sem Sara er sátt með á þessu hljómtæki.
Stigagjöf
|
Hópur |
Stig |
Takmarkanir |
|
1 |
20 |
$R-L \leq 10\, 000$ |
|
2 |
20 |
$k = 1$ |
|
3 |
15 |
$k \leq 2$ |
|
4 |
15 |
$k \leq 3$ |
|
5 |
30 |
Engar frekari takmarkanir. |
| Sample Input 1 | Sample Output 1 |
|---|---|
1 30 2 2 5 |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
17 100 1 7 |
12 |
