[P8649] [蓝桥杯 2017 省 B] k 倍区间

qifan_maker · 2023-04-22 08:15:57 · 题解

题目链接

洛谷

题目解法

如果直接暴力，时间复杂度至少是 \mathcal{O}(n^2)，不能通过此题。

我们需要用到并查集算法。并查集算法比较简单，这里就不过多介绍了，不了解的朋友可以去 OI-wiki 看看。

但是如果枚举 a_r-a_l 还是 \mathcal{O}(n^2)。

我们可以把 a_i \bmod k 的值记录到桶里，每读入一个 a_i，就加上 a_i \bmod k 在桶中出现的次数。

注意：输出时要加上刚好是 k 的倍数的值，也就是 t_0

AC Code

/*
题目编号：
P8649 [蓝桥杯 2017 省 B] k 倍区间
By：
qifan_maker
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    ll a[114514];
    ll t[114514];
    ll sum=0;
    cin >> n >> k;
    for (ll i=1;i<=n;i++){
        cin >> a[i];
        a[i] += a[i-1];
        a[i] %= k;
        sum += t[a[i]];
        t[a[i]]++;
    }
    cout << sum+t[0];
    return 0;
}