网站维护机构,济南网站建设设计公司,搜狗站长平台验证网站,wordpress友情链接调用代码题目描述 给定一个长度为 NN 的数列#xff0c;A1,A2,⋯ANA1,A2,⋯AN#xff0c;如果其中一段连续的子序列 Ai,Ai1,⋯AjAi,Ai1,⋯Aj ( i≤ji≤j ) 之和是 KK 的倍数#xff0c;我们就称这个区间 [i,j][i,j] 是 K 倍区间。 你能求出数列中总共有多少个 KK 倍区间… 题目描述 给定一个长度为 NN 的数列A1,A2,⋯ANA1,A2,⋯AN如果其中一段连续的子序列 Ai,Ai1,⋯AjAi,Ai1,⋯Aj ( i≤ji≤j ) 之和是 KK 的倍数我们就称这个区间 [i,j][i,j] 是 K 倍区间。 你能求出数列中总共有多少个 KK 倍区间吗 输入描述 第一行包含两个整数 NN 和 KK( 1≤N,K≤1051≤N,K≤105 )。 以下 N 行每行包含一个整数 AiAi ( 1≤Ai≤1051≤Ai≤105 ) 输出描述 输出一个整数代表 K 倍区间的数目。 输入输出样例 示例 输入 5 2
1
2
3
4
5输出 6运行限制 最大运行时间2s最大运行内存: 256M 前缀和数组对k取余余数相同时
#include iostream
using namespace std;long long int nums[100100];
int cnt[100100];int main()
{int n, k;long long int res 0;cinnk;for(int i1; in; i){int cur;cincur;nums[i] cur nums[i-1];if(nums[i] % k 0){res;}res cnt[ nums[i] % k ];cnt[ nums[i] % k];}coutres;return 0;
}
两两之间就是k倍子区间
