Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
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łowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |