Bài 3. CẶP MÀ CHIA HẾT CHO K (5,0 điểm; HSG Tin học 9 xã Quang Minh 2026-2027)

Xem dạng PDF

Gửi bài giải

Điểm: 5,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 30M
Input: stdin
Output: stdout

Nguồn bài:
HSG Tin học 9 xã Quang Minh 2026-2027
Dạng bài
Ngôn ngữ cho phép
C# , C++ , Go , Java , Kotlin , Pascal , php , Python 3 , Ruby , Rust , Scratch 3
Check test data again Báo lỗi tại đây

Bài 3. CẶP MÀ CHIA HẾT CHO K (5,0 điểm; HSG Tin học 9 xã Quang Minh 2026-2027)

Câu lạc bộ Tin học có n học sinh, học sinh thứ i có mã số ai. Câu lạc bộ Toán có m học sinh, học sinh thứ j có mã số bj. Mã số trong cùng một câu lạc bộ có thể trùng nhau. Cô tổng phụ trách muốn biết có bao nhiêu cặp (i, j) sao cho tổng ai + bj chia hết cho K. Hai cặp được coi là khác nhau nếu chỉ số học sinh khác nhau.
Dữ liệu:
– Dòng 1: ba số nguyên n, m, K (1 ≤ n, m ≤ 2·105; 1 ≤ K ≤ 109).
– Dòng 2: n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 109).
– Dòng 3: m số nguyên b1, b2, ..., bm (1 ≤ bj ≤ 109).
Kết quả:
– Một số nguyên là số cặp (i, j) thỏa mãn ai + bj chia hết cho K.
Ví dụ:

Dữ liệu vào Dữ liệu ra
5 4 5
12 5 8 20 3
8 1 20 7
5
3 3 3
1 2 3
4 5 6
3

Giải thích:

Ví dụ 1: có năm cặp 12 + 8 = 20, 5 + 20 = 25, 8 + 7 = 15, 20 + 20 = 40, 3 + 7 = 10, đều chia hết cho 5.

Ví dụ 2: có ba cặp 1 + 5 = 6, 2 + 4 = 6, 3 + 6 = 9, đều chia hết cho 3.

Ràng buộc:

  • Có 40% số điểm ứng với các test có n ≤ 1000 và m ≤ 1000.
  • Có 30% số điểm ứng với các test không có ràng buộc thêm về n và m, mọi ai, bj ≤ 1000.
  • Có 30% số điểm còn lại: không có ràng buộc bổ sung.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.