k倍区间蓝桥杯真题python解法
作者: 时间:2023-04-05阅读数:人阅读
题目描述
解题思路
题给一个数字K
如果区间内的合能整除数字K则满足K倍区间
既任意区间的值的和%k==0
既(a[x]-a[y])%k==0 (x,y] (其中a[x]表示前x项求和)(前闭后开的区间)
既只要满足 a[x]%k==a[y]%k就可以
所以我们只需要查找两者前n项求和取模是否相等,如果相等则他们的(x,y]区间可以构成一个k倍空间
我们先观察题给的式例:
题中给出的2倍区间有6个:
123 1234 2345 345 2 4
(0,3】 (0,4】 (1,5】 (2,5】 (1,2】 (4,4】
观察区间规律满足以上我们提出的思想,拿345举例 a[2]=3%2=1 a[5]=15%2=1既(2,5】可以构成一个k倍区间
代码
n, k = map(int, input().split())
#计算前缀和
a = [0]
# 其中,a[0] = 0, dp[0] = 1。
# 这样考虑了单个前缀和构成区间的情况。
dp = {0: 1}#初始化为这样是为了当第一个等于k值出现时除以k时余数为0,包含了单区间的情况
ans = 0
for i in range(1, n + 1):
a.append(a[i - 1] + int(input()))#添加前i项和
amod = a[i] % k
ans += dp.get(amod, 0)#查找是否有与当前相等的余数,有加上模k余数相同的个数,没有则初始化为0
dp[amod] = dp.get(amod, 0) + 1#有则加1,没有则赋值为1
本站所有文章、数据、图片均来自互联网,一切版权均归源网站或源作者所有。
如果侵犯了你的权益请来信告知我们删除。邮箱:licqi@yunshuaiweb.com