F - Subarrays

SDUT 2022 Spring Individual Contest(for 21) - 9 - Virtual Judge

Give you an array of nn positive integers, your task is to count the number of subarrays whose sum is a multiple of kk.

A subarray of array is a sequence a_{l},a_{l+1},...,a_{r}al​,al+1​,...,ar​ for some integers (l,r)(l,r) such that 1leq l leq r leq n1≤l≤r≤n.

Input

The first line contains two positive integers nn (1leq n leq 10^{5})(1≤n≤105), kk (1leq k leq 10^{9})(1≤k≤109).

The second line contains nn positive integers a_1, a_2, cdots, a_na1​,a2​,⋯,an​ (0leq a_i leq 10^{9})(0≤ai​≤109).

Output

Output one line containing one integer indicating the number of subarrays.

Sample 1

6 3
0 1 2 4 7 7

7

Note

For the test

sum[1,1] = 0sum[1,1]=0 , 00 is a multiple of 33

sum[1,3] = 0 + 1 + 2 = 3sum[1,3]=0+1+2=3 , 33 is a multiple of 33

sum[1,6] = 0 + 1 + 2 + 4 + 7 + 7= 21sum[1,6]=0+1+2+4+7+7=21 , 2121 is a multiple of 33

sum[2,3] = 1 + 2 = 3sum[2,3]=1+2=3 , 33 is a multiple of 33

sum[2,6] = 1 + 2 + 4 + 7 + 7= 21sum[2,6]=1+2+4+7+7=21 , 2121 is a multiple of 33

sum[3,4] = 2 + 4 = 6sum[3,4]=2+4=6 , 66 is a multiple of 33

sum[4,6] = 4 + 7 + 7 = 18sum[4,6]=4+7+7=18 , 1818 is a multiple of 33

So the ans is 77.

#include
#define int long long
using namespace std;
const int N=1e5+10;
int n,k,ans;
int a[N],sum;
mapmp;
signed main()
{
    scanf("%lld %lld",&n,&k);
    mp[0]=1;//0%k==0,0是任何数的倍数
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum=sum+a[i];//算出前i个数的和
        sum=sum%k;//分别求出前i个数%k的余数，并用map存起来
        ans+=mp[sum];
        mp[sum]++;
    }
    printf("%lld",ans);
}

 题解：

     代码看似不是前缀和，其实就是前缀和的思想，先把每个位置的前缀和求出来，并用map记录每个位置的前缀和%k的余数，后面如果有余数相等的，就把两个位置的前缀和相减（余数相等减为零）的值一定是k的倍数，比如样例中的1的位置的余数是1，4的位置的余数是1，两位置的前缀和相减得6，是3的倍数。ans+=map[sum],其实就是求的区间的个数，至于为什么map[sum]++在后面，如果加在前面，区间会多算一个。