Kółko informatyczne

Króliki

Grupa starsza

Limit pamięci: 8MB.
Na pewnej planecie żyje para królików. Co roku liczba królików wzrasta dwukrotnie (nawet jeśli jest tylko jeden), pod koniec każdego roku zaś, jeśli (podwojona już) liczba królików na to pozwala, dokładnie 3≤X≤30000000 królików zostaje ewakuowanych rakietą w celu podboju kosmosu, przy czym X jest zawsze liczbą nieparzystą. Króliki zajmują się więc głównie produkcją rakiet - w tym celu dzielą się na grupki po K (2≤K≤1000). W kolejnych latach albo mogą się równo podzielić, albo zostaje kilka królików, które nie mogą utworzyć grupy. Powoduje to głębokie społeczne problemy na wiele lat, dlatego astrolodzy próbują przewidzieć wzorce wystąpień takich zdarzeń na przestrzeni wieków. Twoim zadaniem jest napisanie programu, który, mając dany ciąg długości 1≤N≤1000, znajdzie najbliższe M (1≤M≤10000) takich N-rocznych okresów, że j-ty rok ma równo podzielone króliki wtedy i tylko wtedy, gdy j-ty element ciągu jest równy 0. Okresy te mogą się pokrywać. W roku 1 są 2 króliki.

Wejście

Wyjście

W jedynej linijce wypisz kolejno M najmniejszych (parami różnych) liczb r₁,...,r_M, takich, że liczba królików w roku r_i+j jest podzielna przez K wtedy i tylko wtedy, gdy a_j=0.
Wiadomo, że r_M≤10¹⁸.
W 50% przypadków r_M≤10⁷.
W 90% przypadków X jest liczbą pierwszą.

Przykład 1

1009 4 2 2
0 0 0 0

1 2

Przykład 2

1009 4 2 3
1 0 1 0

17 111

[Zgłoś rozwiązanie]   [Moje zgłoszenia]