Overview

For each integer \(A_i\), we check the remainder when divided by \(K\), and simply count only those with a remainder of \(0\). In other words, we just need to count the number of \(A_i\) such that \(A_i \bmod K = 0\).

Analysis

What this problem requires is determining “whether a given integer is a multiple of \(K\).”

The condition for an integer \(a\) to be divisible by \(K\) is:

\(a \% K = 0\)

For example, when \(K = 3\):

• \(6 \% 3 = 0\), so it is divisible
• \(-6 \% 3 = 0\), so it is divisible
• \(0 \% 3 = 0\), so it is divisible
• \(7 \% 3 \neq 0\), so it is not divisible

Key Insight

Each \(A_i\) can be checked independently. This means no complex processing over the entire array is needed — it is sufficient to examine each element one by one from the beginning.

Comparison with Naive Approaches

For example, approaches such as:

• Generating many multiples of \(K\) and matching against them
• Repeatedly subtracting from \(A_i\) to determine divisibility

would be inefficient since values can be up to \(10^9\).

On the other hand, using the modulo operation %, we can determine “whether it is divisible” in a single check. Therefore, a method that examines each element once in \(O(N)\) time is sufficiently fast.

Algorithm

1. Read \(N, K\)
2. Read the \(N\) integers \(A_1, A_2, \ldots, A_N\)
3. For each \(A_i\), if \(A_i \% K == 0\), increment the count by 1
4. Output the count at the end

For example, given:

• \(N = 5\)
• \(K = 4\)
• \(A = [8, 3, 0, -12, 7]\)

We get:

• \(8 \% 4 = 0\) → count it
• \(3 \% 4 \neq 0\) → don’t count it
• \(0 \% 4 = 0\) → count it
• \(-12 \% 4 = 0\) → count it
• \(7 \% 4 \neq 0\) → don’t count it

So the answer is \(3\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The condition a % K == 0 alone is sufficient for the check.

• As stated in the problem, negative numbers and \(0\) may be included, but this condition correctly handles them.

• Since \(N \leq 5 \times 10^5\) is fairly large, the code uses sys.stdin.buffer.read() for fast input.

  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]
    A = data[2:2 + N]
    ans = sum(1 for a in A if a % K == 0)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.