P8649 [蓝桥杯 2017 省 B] k 倍区间

题目链接：https://www.luogu.com.cn/problem/P8649

方法一：模拟暴力(20分)

#include<bits/stdc++.h>
using namespace std;
const int max_n=100010;
int n, k, a[max_n];
long long ans, s;
int main()
{
	cin>>n>>k;
	for(int i=1; i<=n; i++)cin>>a[i];
	for(int i=1; i<=n; i++){
		s=0;
		for(int j=i; j<=n; j++){
			s=(s+a[j])%k;
			if(s==0)
				ans++;
		}
	}	
	cout<<ans;
	return 0;
 } 

方法二：前缀和

#include<bits/stdc++.h>
using namespace std;
const int max_n=100010;
int n, k, a[max_n];
long long s[max_n];
long long ans, cnt[max_n];
int main()
{
	cin>>n>>k;
	for(int i=1; i<=n; i++)cin>>a[i];
	cnt[0]=1;//初始值 
	for(int i=1; i<=n; i++){
		s[i] = (s[i-1] + a[i])%k;
		cnt[s[i]]++;//统计[0,k)的个数 
	}
	for(int i=0; i<k; i++)
		ans += cnt[i]*(cnt[i]-1)/2;//任意取两个均能相减为0 
	
	cout<<ans;
	return 0;
 }