SỐ DƯ CHO HAI SỐ NGUYÊN 𝑥, 𝑃 (𝑃 > 1). TA ĐÃ BIẾT RẰNG LUÔN T...

Bài 1. Số dư

Cho hai số nguyên 𝑥, 𝑃 (𝑃 > 1). Ta đã biết rằng luôn tồn tại duy nhất cách phân tích: 𝑥 = 𝑘 × 𝑃 + 𝑟 trong đó 𝑘 ∈ ℤ , 𝑟 ∈ {0,1,2, … 𝑃 − 1} . Số 𝑘 được gọi là thương của 𝑥 chia cho P, còn 𝑟 là phần dư của 𝑥 chia cho P. Yêu cầu: Cho trước dãy số nguyên 𝑎

₁

, 𝑎

₂

, … , 𝑎

_𝑛

và hai số nguyên dương 𝑃, 𝑟 . Hãy đếm xem trong dãy đã cho có bao nhiêu số nguyên mà phần dư của nó khi chia cho 𝑃 bằng 𝑟? Dữ liệu: Vào từ file văn bản REMAINDER.INP • Dòng đầu tiên chứa ba số nguyên dương 𝑛, 𝑃, 𝑟 (𝑛 ≤ 10

⁶

, 0 ≤ 𝑟 < 𝑃 ≤ 100) • Dòng thứ hai chứa 𝑛 số nguyên 𝑎

₁

, 𝑎

₂

, … , 𝑎

_𝑛

(|𝑎

_𝑖

| ≤ 10

⁹

) Kết quả: Ghi ra file văn bản REMAINDER.OUT một số nguyên duy nhất là số lượng các phần tử trong mảng có phần dư khi chia cho 𝑃 bằng 𝑟 ? Ví dụ:

REMAINDER.INP

REMAINDER.OUT

5 2 1

3

1 2 3 4 5