DHBB 2026 - DX01 - 10 - Cặp số

Xem dạng PDF

Gửi bài giải

Điểm: 14,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Test chính thức

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho mảng các số tự nhiên ~A = [a_1, a_2, a_3, \dots, a_n]~ và số nguyên ~k~. Cần tìm cặp số ~(l, r)~ sao cho ~l \le r~ và tổng các số trên mảng ~A~ từ vị trí ~l~ đến ~r~ chia hết cho ~k~.

Input

Dòng đầu tiên chứa các số nguyên ~n~, ~k~ ~(1 \le n \le 200000, 2 \le k \le 10^9)~.

Dòng thứ hai chứa các số nguyên ~a_1, a_2, a_3, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

In ra số lượng cặp số ~(l, r)~ thỏa yêu cầu bài toán.

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

6

Bình luận

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



  • 0
    missmphuog  đã bình luận lúc 2, Tháng 11, 2026, 16:19
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n;
        ll k;
        cin >> n >> k;
        unordered_map&lt;ll, ll> cnt;
        cnt.reserve(n + 1);
        cnt[0] = 1;
    
        ll pref = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            ll a;
            cin >> a;
            pref = (pref + a % k) % k;
            ans += cnt[pref];
            cnt[pref]++;
        }
        cout << ans;
        return 0;
    }