Overview

\(N\) visitors receive numbered tickets \(1, 2, \dots, N\) in order. The problem asks you to output, in order, the “lottery ticket numbers” held by visitors whose ticket numbers are multiples of \(K\) (\(K, 2K, 3K, \dots\)).

Analysis

The key point of this problem is to accurately identify “which positions in the data should be output.”

The lottery ticket number of the person with ticket number \(i\) is \(A_i\). Since the people who receive prizes are those whose ticket numbers are multiples of \(K\), the numbers to output are as follows: - 1st person: \(A_K\) - 2nd person: \(A_{2K}\) - 3rd person: \(A_{3K}\) - …

For example, if \(N=6, K=2\) and the lottery ticket numbers are \([10, 20, 30, 40, 50, 60]\), we output the numbers of people whose ticket numbers are multiples of \(2\) (\(2, 4, 6\)), namely \(A_2=20, A_4=40, A_6=60\).

Since \(N\) can be as large as \(2 \times 10^5\), checking each visitor one by one to determine “is the ticket number divisible by \(K\)?” is fast enough, but more efficiently, the ideal approach is to jump every \(K\)-th element to retrieve the values.

Algorithm

1. Read \(N, K\) and \(A_1, \dots, A_N\) from the input.
2. Extract elements from the array (list) whose indices correspond to multiples of \(K\), in order.
   • Note that most programming languages use 0-based indexing, so ticket number \(K\) corresponds to index \(K-1\).
3. Output the extracted numbers separated by spaces.

In Python, the list slicing feature list[start:end:step] allows you to extract elements at a specific step size very quickly and concisely.

Complexity

• Time Complexity: \(O(N)\)
  • Reading all data takes \(O(N)\), and extracting and outputting the prize-eligible visitors takes \(O(N/K)\). Overall, this is \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) input elements.

Implementation Notes

• Fast I/O: Since \(N\) is large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split().

• Using slicing: By writing data[k+1 :: k], you can express in a single line the operation “starting from the position corresponding to ticket number \(K\), retrieve every \(K\)-th element until the end.”

  • In this code, data[0] is \(N\), data[1] is \(K\), and data[2] is \(A_1\), so the first target \(A_K\) is at data[2 + (K-1)], which is data[K+1].

• Unpacking for output: By using print(*ans), you can expand the contents of the list and output them separated by spaces.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字（スペース、改行など）で分割してリストにします。
    # N（来場者数）と K（景品の倍数）が20万程度と大きいため、一括読み込みが効率的です。
    data = sys.stdin.read().split()
    
    # 入力が空の場合や不足している場合の例外処理
    if len(data) < 2:
        return
    
    # K はリストの2番目の要素（インデックス 1）です。
    k = int(data[1])
    
    # くじ引き券の番号 A_1, A_2, ..., A_N は data[2] 以降に格納されています。
    # 整理番号が K の倍数である来場者は、K番目、2K番目、3K番目... の来場者です。
    # これらは A_K, A_2K, A_3K, ... のチケット番号を持っています。
    # リスト data におけるそれぞれのインデックスは以下の通りです：
    # A_1  -> インデックス 2
    # A_2  -> インデックス 3
    # ...
    # A_K  -> インデックス 2 + (K - 1) = K + 1
    # A_2K -> インデックス 2 + (2K - 1) = 2K + 1
    # したがって、インデックス K + 1 から K 刻みでスライスすることで、
    # 景品をもらえる来場者のチケット番号を順番に抽出できます。
    ans = data[k + 1 :: k]
    
    # 結果が存在する場合、スペース区切りで1行に出力します。
    # Pythonの * 演算子（アンパック）を使うことで、リストの要素をスペース区切りで出力できます。
    if ans:
        print(*(ans))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.