Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_07_15 - Sfeniczne i nie tylko

Miałeś już okazję zapoznać się z liczbami sfenicznymi chociażby rozwiązując jedno z zadań próbnym VII edycji konkursu "FRAKTAL". Przypomnijmy: liczba sfeniczna, to taka liczba naturalna, która rozkłada się na iloczyn dokładnie trzech różnych liczb pierwszych. Utrudnijmy to zadanie i zdefiniujmy liczbę k-sfeniczną. Liczbę k-sfeniczną nazywamy taką, która rozłoży się na iloczyn dokładnie k różnych liczb pierwszych. Zadanie polega na napisaniu programu, który będzie odpowiadać na pytanie, ile podano liczb k-sfenicznych w ciągu liczb naturalnych dodatnich począwszy od indeksu w przedziale [a..b], gdzie a to indeks początkowy przedziału, natomiast b to indeks końcowy (wyrazy ciągu indeksujemy od 1).

Wejście

W pierwszym wierszu jedna liczba naturalna n określająca długość ciągu (nie więcej niż milion).

W drugim wierszu n liczb naturalnych dodatnich nie większych niż milion.

Następnie jedna liczba q określająca liczbę zapytań. Każde zapytanie składa się z trzech liczb całkowitych a, b i k takich, że 1 ≤ a b n definiujących przedział [a..b] oraz 1 ≤ k ≤ 20, określająca ilość liczb pierwszych w rozkładzie badanych liczb.

Wyjście

Dla każdego zapytania jedna liczba określająca liczbę liczb sfenicznych o k rozkładzie.

Przykład

Wejście:
7
3 6 8 9 20 13 80
5
1 7 3
1 7 1
2 6 2
5 7 3
1 1 1

Wyjście:
0
2
1
0
1

Dodane przez:Marcin Kasprowicz
Data dodania:2017-04-07
Limit czasu wykonania programu:1s-2.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

ukryj komentarze
2017-04-08 21:02:37 Marcin Kasprowicz
dla 2 6 2, jedyną liczbą spełniająca kryteria zadania jest 6 = 2 * 3, rozkład na dwie różne liczby pierwsze
2017-04-08 20:44:08 Rafał Darłak
Jak dobrze rozumiem w przykładowym teście dla zapytania o przedział 2 6, k = 2 odpowiedź to 1, ponieważ 20 rozkłada się na 2^2 * 5^1, tak? Czyli każda liczba pierwsza może wystąpić tylko raz jako mnożnik?
2017-04-08 20:21:07 Marcin Kasprowicz
Skoro nie masz AC, tzn., że twój program nie przeszedł wszystkich testów!
2017-04-08 19:52:41
Moj program przeszedl wszystkie testy. Dlaczego nie mam ACC?
2017-04-08 18:34:33 Marcin Kasprowicz
http://ideone.com/0RfNdO
2017-04-08 18:09:17
Mozna prosic o wiecej testow?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.