精选一百道备赛蓝桥杯——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倍区间。
  

代码实现

1. #include <iostream>
2. using namespace std;
3. long long a[100010];
4. long long cnt[100010];
5. long long ans = 0;
6. int main()
7. {
8.   cnt[0]++;
9.   int n, k; cin >> n >> k;
10.   for(int i = 1; i <= n; i++){
11.     cin >> a[i];
12.     a[i] += a[i-1];
13.   }
14.   
15.   for(int i = 1; i <= n; i++)  ans += cnt[a[i] % k]++;
16.   cout << ans;
17.   return 0;
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。