k倍区间:前缀和

[蓝桥杯][2017年第八届真题]k倍区间

题目描述

给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。

你能求出数列中总共有多少个K倍区间吗?

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出

输出一个整数,代表K倍区间的数目。

样例输入

5 2
1
2
3
4
5

样例输出

6

题目描述:

定理1:n个数,从里边取两个,共有n*(n-1)/2种方法

定理2:前缀和的余数相同,那两个区间相减,中间的区间肯定是k的倍数,例如例题中12和12345,两个前缀和余数都为1,那么两个区间相减也就是345肯定是2的倍数

/*
* @Issue: https://www.dotcpp.com/oj/problem1882.html
* @Author: 一届书生
* @LastEditTime: 2020-02-19 11:11:15
*/
#include<iostream>
using namespace std;
const int maxn = 100010;
#define ll long long
ll n, k,t, q[maxn],cnt[maxn],qian=0;
int main() {
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++) { //从1开始,方便后边处理
scanf("%lld", &t);
qian = (qian + t); //求输入数组前缀
q[qian%k]++; //求前缀和的取余,并用桶排序、统计个数
}
ll flag = 0;
for (int i = 0; i < k; i++) {
if(q[i])
flag += (q[i] * (q[i] - 1) / 2); //n个数,从里边取两个,共有n*(n-1)/2种方法
} cout << flag +q[0]<< "\n"; // 为什么要加q[0]?
// 因为我们前边漏掉了前i个数的和对k取模为0的情况
//也就是漏掉了例题中123和1234的这两个情况。
return 0;
}

  

上一篇:Python : 标准库-日期和时间


下一篇:Linux下汇编语言学习笔记2 ---