2017蓝桥杯 K倍区间 前缀和+同余定理

2017蓝桥杯 K倍区间 前缀和+同余定理

给定一个长度为的数列，。
如果其中一段连续的子序列之和是的倍数，我们就称这个区间是倍区间。
你能求出数列中总共有多少个倍区间吗？

看到“区间的和”，首先想到前缀和，然后暴力枚举区间计数。

#include <bits/stdc++.h>
#define
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    vector<int> a(n + 1); a[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] += a[i - 1];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            if((a[j] - a[i - 1]) % k == 0) ans++;
    return cout << ans << endl, 0;
}

显然这是个暴力求解的思路，结合题目所给数据范围：$(1 <= N, K <= 100000) ,(1 <= Ai <= 100000) $，果不其然的TLE了。那么考虑如何进行优化。

我们首先引入同余方程的概念：

同余方程是一个数学方程式。该方程式的内容为：对于一组整数，里的每一个数都除以同一个数，得到的余数可以为,共种。我们就以余数的大小作为标准将分为类。每一类都有相同的余数。

同余方程的结论：

1. 如果，那么;
2. 如果，那么；

那么利用同余方程的两个结论，我们可以对前缀和进行优化：

根据结论1，我们可以在求前缀和的过程中进行取模运算；

根据结论2，我们可以推出：可以得到如果区间和和区间和都可以被整除，的区间和也可以被整除。

那面根据当两个数的余数相同时，这两个数的差的余数为0，我们可以统计不同余数的个数，然后求全排列即可。

#include <bits/stdc++.h>
#define
using namespace std;
const int N = 100005;
int cnt[N];

signed main(){
    ios_base::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    vector<int> a(n + 1); a[0] = 0;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = (a[i] + a[i - 1]) % k;
        cnt[a[i]]++;
    }
    for(int i = 0; i < k; i++){
        ans += (int)cnt[i] * (int)(cnt[i] - 1) / 2;
    }
    return cout << ans + cnt[0] << endl, 0;
}