题目描述

blablabla

样例

n,k=map(int,input().split())
pre_sum=[0]*(n+1)
dic={0:1}   #注意这里需要初始化，因为，前缀和模k=0时，本身就是一个解，必须先加一个，不然下面一个自身无法构成解
res=0
for i in range(1,n+1):
    pre_sum[i]=int(input())
    pre_sum[i]+=pre_sum[i-1]

    reminder=pre_sum[i]%k

    if reminder not in dic:
        dic[reminder]=0

    res+=dic[reminder]
    dic[reminder]+=1

print(res)

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla