蓝桥杯 k倍区间
题目描述
给定一个长度为 N 的数列，A1,A2,⋯AN，如果其中一段连续的子序列 Ai,Ai+1,⋯Aj ( i≤j ) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入描述
第一行包含两个整数 N 和 K( 1≤N,K≤ )。
以下 N 行每行包含一个整数 Ai ( 1≤Ai≤)
输出描述
输出一个整数，代表 K 倍区间的数目。
输入输出样例
示例
输入
5 2
1
2
3
4
5
输出
6
思路：
-
计算前缀和数组S。
-
对于每个S[j]，计算S[j] % K。
-
统计在此之前有多少个S[i]（i < j）满足S[i] % K == S[j] % K。
-
将所有这样的数量累加，就是总的K倍区间数。
任何两个前缀区间的和对k取模的值相等，则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间
因此对具有区间和%k值相等任何两个区间进行组合，再将这些值加起来就得到结果
证明： 假设一个数列为a1,a2,a3,....,an，一个小的前缀区间s1为a1,a2,a3,....,ap,还有一个大的前缀区间s2为a1,a2,a3,...,a(p+m)，当我们对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;typedef long long ll;
int n, k;
const int N = 1e5+10;
ll a[N];
ll cnt[N];
ll ans;int main()
{cin>>n>>k;for(int i=1; i<=n; ++i){cin>>a[i];a[i] += a[i-1]; //前缀和数组cnt[a[i]%k]++; //cnt[i]：余数 i 出现的次数}ans = cnt[0];//遍历余数 for(int i=0; i<k; ++i){ans += (cnt[i]*(cnt[i]-1))/2;//组合数求法，n个区间任取两个的情况：n*(n-1)/2 }cout<<ans;return 0;
}