P8649 [蓝桥杯 2017 省 B] k 倍区间 - 洛谷
题目描述
给定一个长度为 N 的数列，A1,A2,…,AN，如果其中一段连续的子序列 Ai,Ai+1,…,Aj(i≤j) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K (1≤N,K≤105)。
以下 N 行每行包含一个整数 Ai (1≤Ai≤105)。
输出格式
输出一个整数，代表 K 倍区间的数目。
输入输出样例
输入 #1
markdown
5 2
1
2
3
4
5输出 #1
markdow
6说明/提示
时限 2 秒，256M。蓝桥杯 2017 年第八届
思路：
前缀和+同余定理
代码如下：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll a[N],pre[N],cnt[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n,k;cin >> n >> k;for(ll i = 1 ; i <= n ; i++){cin >> a[i];pre[i] = (pre[i-1] + a[i])%k;cnt[pre[i]]++;}cnt[0]++;ll ans = 0;for(ll i = 0 ; i < k ; i++){ans += cnt[i]*(cnt[i] - 1)/2; } cout << ans;return 0;
}
