题目描述

给定一个长度为 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

先像一个暴力做法，再不断优化
n^3（暴力）->n^2（开前缀和判断%k==0）->n(再开一个前缀和cnt，存余数是x有多少个)

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int n,k;
ll s[N],cnt[N];//s[i]记录i的前缀和，cnt[]记录余数的个数

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
    }
    ll res=0;
    cnt[0]=1;//l<=r
    for(int r=1;r<=n;r++)//区间的右端点
{
    res+=cnt[s[r]%k];
    cnt[s[r]%k]++;
}    
    printf("%lld",res);

    return 0;
}