精选一百道备赛蓝桥杯——2.K倍区间
解题思路
- 任何两个前缀区间的和对k取模的值相等，则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间。
- 因此我们可以对具有区间和%k值相等任何两个区间进行组合，再将这些值加起来就得到结果！
- 证明： 假设一个数列为a1,a2,a3,…,an，一个小的前缀区间s1为a1,a2,a3,…,ap,还有一个大的前缀区间s2为a1,a2,a3,…,a(p+m)，p,p+m<n。
- 当我们对s1、s2的和分别取模，得到(a1+a2+a3+…+ap)%k和(a1+a2+a3+…+ap+m)%k，当这两个值相等的时候。
- 我们则可以列出这个等式：(a1+a2+a3+…+ap)%k-(a1+a2+a3+…+ap+m)%k=0，根据取模也具有分配律可得到，(a1+a2+a3+…+ap-a1-a2-a3-…-ap+m)%k=0。
- 因此可以推出结论，s2-s1得出的区间必定为k倍区间。
代码实现
#include <iostream>
using namespace std;
long long a[100010];
long long cnt[100010];
long long ans = 0;
int main()
{
cnt[0]++;
int n, k; cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] += a[i-1];
}
for(int i = 1; i <= n; i++) ans += cnt[a[i] % k]++;
cout << ans;
return 0;
}