题目描述
给定一个长度为 �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 倍区间的数目。
输入输出样例输入 #15 21 2 3 4 5 输出 #16说明/提示时限 2 秒, 256M。蓝桥杯 2017 年第八届
题解:没开longlong老错一个点,运用到同余定理:如果a%k==b%k 则由|a-b|%k==0
#includeusing 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