蓝桥杯2017年第八届真题-k倍区间 （C++代码）

解题思路:

注意事项:

参考代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
int N,K;
ll ans = 0;
int a[100000+5]; 
int S[100000+5]; //S[i]表示a[1]到a[i]的和
int cnt[100000+5]; //cnt[i]表示S模K为i的数的个数 
void solve()
{
	for(int i=1; i<=N; ++i)
	{
		S[i] = (S[i-1] + a[i])%K;
		ans += cnt[S[i]];
		cnt[S[i]]++;	
	} 
	cout<<ans+cnt[0]<<endl;
} 
int main()
{
	scanf("%d%d",&N,&K);
	memset(S,0,sizeof(S));
	memset(cnt,0,sizeof(cnt));
	int t = N;
	int i = 1; //从1开始 
	while(t--)
	{
		scanf("%d",&a[i]);
		i++;
	}
	solve();
	return 0;	
}