文章目录

1题目：

标题： k倍区间

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … 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

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

2思路：

  • 定义presum为前缀和数组，

  • 定义l为区间左端点，r为右端点，区间[l,r]的和即

  •                 presum[r] - presum[l-1]

  • 要求能够整除k的区间，即求 (presum[r] - presum[l-1])%k==0的个数

  • 上式等价于presum[l-1]%k ==presum[r]%k

  • 所以等价于求前缀和数组中模k得到的值相同的区间的对数
    例如样例的5 2
    1 2 3 4 5
    第i各位置的模2，结果是1，那么看它前面有几个模2是1，若有2个，则可以与这个位置构成两个2倍区间

3代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+9; 
int A[N];
int presum[N] = {0};
int main()
{
	int n,k;
	cin>>n>>k;
	int ans = 0;
	int cnt[N];//cnt[i]统计前缀后中模k结果为i的个数 
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
		presum[i]+=A[i];
		presum[i]%=k;
		ans+= cnt[presum[i]];//ans要在cnt++前执行 
		cnt[presum[i]]++;
	}
	//接下来要加上前缀和中模k==0个个数，因
	//为如果他模k==0,则这个前缀和就是一个k倍区间啊 
	cout<<ans+cnt[0]<<endl;
	return 0;
}