题目描述
给定一个长度为 NN 的数列，A1,A2,⋯ANA1,A2,⋯AN，如果其中一段连续的子序列 Ai,Ai+1,⋯AjAi,Ai+1,⋯Aj ( i≤ji≤j ) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 KK 倍区间吗？
输入描述
第一行包含两个整数 N 和 K( 1≤N,K≤10 1≤N,K≤10 )。
以下 N 行每行包含一个整数 AiAi ( 1≤Ai≤，
1≤Ai≤
)
输出描述
输出一个整数，代表 K 倍区间的数目
输入输出样例
示例
输入
5 2
1
2
3
4
5
输出
6首先想到的是暴力for(for（）)，两个数组去求，先从第一个数开始，加到最后一个，再从第二个开始，加到最后一个。问题就是会超时。
这个算法利用的是前缀和的知识，每一项都加上前一项，直到最后一项，求出所有的前缀和
从i>0开始，
求出每一项加上前一项的前缀和，
求出次和模的余数，将余数作为数组的下标，求出所有余数数量
用到一个重要知识点：任何两个前缀区间的和对k取模的值相等，则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间（在官网上看到的题解，感觉思路很好）
任何两个前缀区间的个数=（n*(n-1)）/2，n=res[i];
注：1.不要忘记a[0],也要进行取模，res++；
2.类型要用 long long
#include<bits/stdc++.h>
using namespace std;const int N=1e5+100;
typedef long long int ll;
int main()
{// 请在此输入您的代码int n,k;cin>>n>>k;ll a[N];ll sum=0;ll res[N]={0};for(int i=0;i<n;i++){cin>>a[i];if(i>0){a[i]+=a[i-1];//求和}res[a[i]%k]++;}sum=res[0];for(int i=0;i<k;i++){sum+=(res[i]*(res[i]-1))/2;}cout<<sum;return 0;
}