Overview

For each of the given \(N\) integers, determine whether it is divisible by a positive integer \(K\) (i.e., the remainder is 0), and count how many satisfy this condition. This can be solved by checking each element once.

Analysis

The key point is that “\(a\) is divisible by \(K\)” is equivalent to \(a \bmod K = 0\). Therefore, for each \(A_i\), we check A_i % K == 0 and increment the count if it is true.

For example, when \(K=3\) and the array is \([6, -6, 7, 0]\):

• \(6 \% 3 = 0\) → divisible
• \(-6 \% 3 = 0\) → divisible
• \(7 \% 3 \neq 0\) → not divisible
• \(0 \% 3 = 0\) → divisible (0 is divisible by any positive integer)

Thus the answer is 3.

In this problem, it is sufficient to look at each element just once. Since the constraint is \(N \le 5 \times 10^5\), a brute-force approach (single loop) runs fast enough. Conversely, using unnecessarily complex operations (sorting or nested loops) would add waste.

Algorithm

1. Read \(N, K\) and the array \(A\) from input.
2. Initialize a counter cnt = 0.
3. For each element a, if a % k == 0, then cnt += 1.
4. Output cnt at the end.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (because the implementation stores the array; this can be reduced to \(O(1)\) with sequential processing)

Implementation Notes

• Negative numbers and 0 can be handled directly with % without any issues.

• Since the input size is somewhat large, using fast input with sys.stdin.buffer.read() is effective.

• Using arr = data[2:2+n] to extract exactly \(N\) elements is also a safe practice.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n, k = data[0], data[1]
    arr = data[2:2 + n]

    cnt = 0
    for a in arr:
        if a % k == 0:
            cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.