1882: 蓝桥杯2017年第八届真题-k倍区间(3.17)

解题思路:如果把所有区间分为k倍区间和非k倍区间,观察一下他们之间的区别,k倍区间的和modk后等于0,而非k倍区间的和modk后等于n,n是介于1至k-1的数.再来思考一下如何得到k倍区间,第一种情况,本身就是k倍区间,不那么用做任何操作,第二种情况,本身是非k倍区间,我们需要通过组合两个(为什么是两个,不是多个呢?请读者自行思考,才能理解算法过程)连续(包含关系)的非k倍区间,来消除n的影响,那么两区间之间部分就成为k倍区间.

注意事项:我是用C++AC的,时间复杂度在O(n)下,python都会超时,题解仅提供python的写法,便于理解

参考代码:

n, k = map(int, input().strip().split())
modk = [0 for i in range(k)]
prefix = 0 #前缀和
count = 0
for i in range(n):
    temp = int(input().strip())
    prefix += temp
    modk[prefix % k] += 1 # 统计前缀和modk结果相同的区间数,即同类非k倍区间,同类是为了消除n的影响
for j in range(k):
    count += modk[j] * (modk[j] - 1) // 2 # 等差数列求和公式,或者C(n,2)组合
count += modk[0]#本身就是k倍区间无需组合
print(count)