26792번 - Liczby względnie pierwsze 다국어

Bajtazar zafascynował się ostatnio zagadnieniem liczb względnie pierwszych. Przypomnijmy, że liczba naturalna x jest względnie pierwsza z liczbą naturalną y, jeśli największy wspólny dzielnik liczb x i y jest równy 1. Na przykład liczbami względnie pierwszymi z 10 są

1, 3, 7, 9, 11, 13, 17 . . .

Bajtazar wypisał wszystkie liczby względnie pierwsze z liczbą n w kolejności rosnącej. Taką listę oprawił sobie w ramkę i od dziś nazywa ją listą Bajtazara.

Zanim swoje dzieło powiesi na ścianie, dla pewności jednak wypadałoby sprawdzić poprawność listy. Ponieważ lista ta jest nieskończona, Bajtazar chciałby tylko wyrywkowo sprawdzić jej poprawność na pewnym fragmencie długości c, zaczynając od pozycji k-tej. Elementy listy numerujemy kolejnymi liczbami, począwszy od 1. Czy pomożesz mu w tym zadaniu?

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne n, k oraz c (2 ≤ n ≤ 10¹⁴, 1 ≤ k ≤ 10¹⁴, 1 ≤ c ≤ 100 000) określające kolejno: liczbę wybraną przez Bajtazara, pozycję początkową sprawdzanego fragmentu oraz długość sprawdzanego fragmentu listy Bajtazara.

Twój program powinien wypisać na wyjście c liczb naturalnych pooddzielanych pojedynczymi odstępami – kolejne elementy na pozycjach k, (k + 1), (k + 2), . . ., (k + c − 1) na liście Bajtazara, która – przypomnijmy – zawiera liczby względnie pierwsze z n, wypisane w kolejności rosnącej.

Wyjaśnienie do przykładu: Bajtazar pyta o elementy na pozycjach 3, 4, 5 oraz 6 na swojej liście. Lista Bajtazara w tym przypadku (dla n = 10) składa się kolejno z liczb 1, 3, 7, 9, 11, 13, 17 . . .