杭州软件网站建设,微信小程序怎么做会员卡,外贸seo推广,山东联通网站备案题目描述
给定一个长度为N的数列#xff0c;A1, A2, … AN。 如果其中一段连续的子序列Ai, Ai1, … Aj(i j)之和是K的倍数#xff0c;我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗#xff1f; 输入 第一行包含两个整数N和K。(1 N, K …题目描述
给定一个长度为N的数列A1, A2, … AN。 如果其中一段连续的子序列Ai, Ai1, … Aj(i j)之和是K的倍数我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗 输入 第一行包含两个整数N和K。(1 N, K 100000) 以下N行每行包含一个整数Ai。(1 Ai 100000)
输出
输出一个整数代表K倍区间的数目。
样例输入
5 2 1 2 3 4 5
样例输出
6
解题思路: 我们拿这个数论为4 4 4 4 ,模拟一下for循环的过程就知道为什么这样写了很巧妙!!!
代码如下
#include iostream
using namespace std;
typedef long long ll;
const int N 100010;
ll cnt[N],s[N];
int main()
{int n,k;cinnk;for (int i 1;in;i){cins[i];s[i] s[i-1];}ll res 0;cnt[0] 1;for (int i 1;in;i){res cnt[s[i]%k];cnt[s[i]%k];}coutresendl;return 0;
}
