蓝桥杯 6. k倍区间
k倍区间原题目链接
题目描述
给定一个长度为 N 的数列 A₁, A₂, ⋯, Aₙ，如果此中一段连续的子序列 Aᵢ, Aᵢ₊₁, ⋯, Aⱼ (i ≤ j) 之和是 K 的倍数，我们就称这个区间 是 K 倍区间。
请你求出数列中总共有多少个 K 倍区间。
输入描述
[*]第一行包含两个整数 N 和 K (1 ≤ N, K ≤ 10⁵)。
[*]接下来 N 行，每行一个整数 Aᵢ (1 ≤ Aᵢ ≤ 10⁵)，表示数列的每个元素。
输出描述
输出一个整数，表示 K 倍区间的数量。
输入样例
5 2
1
2
3
4
5
输出样例
6
c++代码
#include<bits/stdc++.h>#include<stdio.h>using namespace std;typedef long long ll;ll N, K, ans 
1; 0;unordered_map<int, int> mp;vector<ll> arr;int main() { scanf("%lld %lld", &N, &K); arr 
1; vector<ll>(N + 1, 0); for (ll i 
1; 1; i <
1; N; i++) { scanf("%lld", &arr); arr +
1; arr; } if (K 
1;
1; 1) { printf("%lld", (N * (N - 1)) / 2 + N); return 0; } for (int i 
1; 0; i <
1; N; i++) mp % K]++; for (auto it 
1; mp.begin(); it !
1; mp.end(); it++) ans +
1; ((it->second * (it->second - 1)) / 2); printf("%lld", ans); return 0;}//by wqs 算法解析
起首前缀和想得到吧
for (ll i 
1; 1; i <
1; N; i++) { scanf("%lld", &arr); arr +
1; arr;} 现在有了前缀和数组
我们要找两个端点i, j，使得
(arr - arr) % k 
1;
1; 0假设arr % k 
1; c, arr % k 
1; d，根据取模公式(arr - arr) % k 
1; c - d。也就是我们要让c - d 
1; 0，也就是c 
1;
1; d。现在我们的任务转换为求有多少组i，j满意arr % k 
1;
1; arr % k。 for (int i 
1; 0; i <
1; N; i++) mp % K]++;for (auto it 
1; mp.begin(); it !
1; mp.end(); it++) ans +
1; ((it->second * (it->second - 1)) / 2);//排列组合printf("%lld", ans);
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]