MAXDIV - Đếm đoạn chia hết

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 498M
Tác giả:
bvquoc
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho số nguyên dương ~k~ và một dãy gồm ~N~ số nguyên dương~a_1, a_2, ..., a_n~. Tìm số cặp số nguyên dương (~l, r~) với ~l~ ≤ ~r~, sao cho trong các số từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.

Input

  • Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~k~ (~N~ ≤ ~3*10^5~, ~k ≤ 10^9~).
  • Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~(~a_i ≤ 10^9~).

Output

  • Một dòng duy nhất gồm số lượng cặp số (~l~, ~r~) thỏa mãn đề bài.

Sample

Input #1
5 2
1 2 3 4 5
Output #1
11

Hint

Giải thích:

  • Các cặp số (~l, r~) thỏa mãn là: ~(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,4), (3,5), (4,4), (4,5), (5,5)~.

Ràng buộc:

  • Subtask 1 (20% số test): ~N~ ≤ 200
  • Subtask 2 (40% số test): ~N~ ≤ 2000
  • Subtask 3 (40% số test): Không có ràng buộc gì thêm.

Problem source: Free Contest 120

Bình luận

Please read the guidelines before commenting.


  • 0
    MANHOOH  đã bình luận lúc 19, Tháng 10, 2025, 8:39 ← sửa 5

    lưu các vị trí các số chia hết cho k vào mảng idx rồi tính 2 trường hợp ko phần tử nào chia hết cho k và có đúng 1 phần tử chia hết cho k 

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), idx = {0};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] % k == 0) idx.push_back(i + 1);
    }
    idx.push_back(n + 1);

    ll res = 0;

    for (int i = 0; i + 1 < idx.size(); i++) {
        ll len = idx[i + 1] - idx[i] - 1;
        res += len * (len + 1) / 2;
    }

    for (int i = 1; i + 1 < idx.size(); i++) {
        res += (idx[i] - idx[i - 1]) * (idx[i + 1] - idx[i]);
    }

    cout << res;
}

  • 0
    M1nK_08  đã bình luận lúc 8, Tháng 12, 2024, 6:07

    dùng kĩ thuật: Tìm kiếm nhị phân O(nlogn) hoặc Hai Con Trỏ O(2n) nhé


  • 0
    bop2401  đã bình luận lúc 20, Tháng 10, 2024, 2:18 ← chỉnh sửa

    đề hay quá


  • 0
    bop2401  đã bình luận lúc 20, Tháng 10, 2024, 2:18 ← sửa 2

    đề thật sáng tạo


  • 3
    tiennv  đã bình luận lúc 5, Tháng 10, 2024, 9:39

    đề bảo tối đa 1 số chia hết cho k tức là có thể 0 số nào chia hết hoặc chỉ 1 số duy nhất.


  • 0
    Higa_Wateru  đã bình luận lúc 5, Tháng 1, 2024, 15:57

    cặp (1,1) sao chia hết cho 2 đc


  • 0
    161007thanhhiu  đã bình luận lúc 19, Tháng 10, 2023, 13:15

    đề giải thích gì kì v