题目描述
求k倍区间的个数
思路分析
求区间和一定有前缀和,先得到前缀和
由于(S[r]-S[l-1])%K == 0 => S[r]%k == S[l-1]%k,因此余数一样时候就会是一个K倍区间
并且求个数时候比如有两个位置一样,那就是1,三个位置一样就是3=1+2,四个位置一样就是C(4,2)=6=1+2+3;对于一个位置的如果刚好是k倍区间就从1开始,其他从0开始
(前缀和) $O(n)$
两步都是o(n),并且分开的
python 代码
# 1.得到前缀和
N,K = map(int,input().split())
re = [0 for i in range(N+1)]
st = [0 for i in range(K)] # 余数为i的个数
st[0] = 1 # 因为当就算一个余数为0时候,也要加1
for i in range(1,N+1):
re[i] = re[i-1] + int(input())
# 2.求个数
res = 0
for i in range(1,N+1):
res += st[re[i]%K]
st[re[i]%K] += 1
print(res)