题目描述

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

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

 看到这道题首先就想到不停地遍历，找到符合条件的就可以计数

#include <bits/stdc++.h>
using namespace std;int N;
int a[100000];
int K;
int ans;
int main()
{cin>>N>>K;for(int i=0;i<N;i++){cin>>a[i];}for(int i=0;i<N;i++){if(a[i]%K==0){ans++;}for(int j=i+1;j<N;j++){a[i]=a[i]+a[j];if(a[i]%K==0){ans++;}}}cout<<ans;return 0;
}

 当然，通过分析，两层for循环时间复杂度为O（n*n），运行超时

所以，只能想办法找到更好的办法

 

 正确代码：（用到排列组合知识）

#include <bits/stdc++.h>
using namespace std;
long long mod[100010]={0},add[100010]={0};
long long sum=0,a[100010];
int main()
{int n,k;long long cnt=0;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){sum=sum+a[i];mod[i]=sum%k;add[mod[i]]++;}for(int i=0;i<n;i++){cnt+=add[i]*(add[i]-1)/2;}cout<<cnt+add[0];return 0;
}