【洛谷 8649】 [蓝桥杯 2017 省 B] k 倍区间

题目描述

给定一个长度为 �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 倍区间的数目。

输入输出样例

5 2
1  
2  
3  
4  
5  

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;
}