题目描述
给定一个长度为 �N 的数列，�1,�2,⋯��A1,A2,⋯AN，如果其中一段连续的子序列 ��,��+1,⋯��(�≤�)Ai,Ai+1,⋯Aj(i≤j) 之和是 �K 的倍数，我们就称这个区间 [�,�][i,j] 是 �K 倍区间。
你能求出数列中总共有多少个 �K 倍区间吗？
输入格式
第一行包含两个整数 �N 和 �K(1≤�,�≤105)(1≤N,K≤105)。
以下 �N 行每行包含一个整数 ��Ai(1≤��≤105)(1≤Ai≤105)。
输出格式
输出一个整数，代表 �K 倍区间的数目。
输入输出样例
输入 #1
5 2 1 2 3 4 5
输出 #1
6
说明/提示
时限 2 秒, 256M。蓝桥杯 2017 年第八届
题解：没开longlong老错一个点，运用到同余定理：如果a%k==b%k 则由|a-b|%k==0
#include<bits/stdc++.h> using namespace std; const int N=100003; long long a[N],n,k,ans; long long sum; long long b[N]; int main(){ freopen("8649.in","r",stdin); freopen("8649.out","w",stdout); scanf("%lld %lld",&n,&k); b[0]=1; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum=(sum+a[i])%k; b[sum]++; } /*for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) if((f[j]-f[i])%k==0) ans++;*/ for(int i=0;i<k;i++){ ans+=(b[i]*(b[i]-1))/2; } printf("%lld",ans); return 0; }