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,我们可以推出:可以得到如果区间和和
区间和都可以被
整除,
的区间和也可以被
整除。
那面根据当两个数的余数相同时,这两个数的差的余数为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;
}