AcWing 1230. K倍区间
原题链接
中等
作者:
1w7p
,
2024-03-28 20:35:55
,
所有人可见
,
阅读 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
static StringTokenizer st;
public static int next() throws IOException {
while(st==null||!st.hasMoreTokens())
st=new StringTokenizer(in.readLine());
return Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws IOException {
int n = next();
int k = next();
int[] m = new int[n];
long[] sum = new long[n + 1];
for (int i = 0; i < n; i++)
m[i] = next();
sum[0] = m[0];
for (int i = 1; i < n; i++) {
sum[i] = sum[i-1] + m[i];
sum[i-1]%=k;
}
sum[n-1]%=k;
long count = 0;
int[] cnt=new int[n];
cnt[0]++;//如果%k==0说明是k倍区间,要+1
for(int i=0;i<n;i++){
count+=cnt[(int) (sum[i]%k)];
cnt[(int) (sum[i]%k)]++;
}
out.println(count);
out.flush();
}
}