题目描述

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

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

输入格式
第一行包含两个整数 N和 K。

以下 N行每行包含一个整数 Ai。

输出格式
输出一个整数，代表 K倍区间的数目。

数据范围
1≤N,K≤100000,
1≤Ai≤100000

输入样例：
5 2
1
2
3
4
5
输出样例：
6

样例

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+10;//不加这10会越界，不ac
int a[N],n, k;
ll  s[N];
int cnt[N];//相同余数的个数

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)//注意细节：前缀和默认从1开始
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];//防止这里越界0-1
    ll res = 0;
    for (int i = 1; i <= n; i++) {

    //if(cnt[i]%2==0)
    res += cnt[s[i] % k]; //把余数相同的放到一个里面，只要余数相同，说明都可以组成一个区间
        cnt[s[i] % k]++;//当遍历一半的时候，余数都会加+1
        //记录s[i]%k的余数的个数
    //printf("%lld", res);
//printf("%d:%d\n",s[i],cnt[s[i]%k]);   
}for (int i = 1; i <= n; i++) 
if(s[i]%k==0)
res++;//i的前缀和本身就能除尽，i的前缀和本身就是一个区间。
    printf("%lld", res);
}

a 1 2 3 4 5

s[i] 1 3 6 10 15

s[i]%k 1 1 0 0 1

这时，同余的情况一共有4种

（1,1) (1,1) (1,1) (0,0)

此时是res[s[i]]=4

而单个s[i]%k==0依然是满足题意的

也就是那两个0 res[s[i]]+res[0]=6

相通之后真的很简单，相通之前真的很痛苦

希望对大家能有一点帮助

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla