【Python训练营】Python每日一练----第31天: k倍区间

????????????????????????
????????????Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照????????????

????​​​入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！????????????​​​ ????​​最后，愿我们都能在看不到的地方闪闪发光，一起加油进步????????????​​​ ????????????“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~????????????
????????????✨✨✨

​​前言：​​【Python训练营】是针对Python语言学习所打造的一场​刷题狂欢party！​ 对基础知识把握不牢固的话，欢迎参考此套课程：​​​Python公开课​​​ 搭配使用最佳嗷~喜欢的话就抓紧订阅起来吧！????????????如果对学习没有自制力或者没有一起学习交流的动力，欢迎私信或者在文末添加我的VX，我会拉你进学习交流群，我们一起交流学习，报团打卡

Python每日一练：

• ​​题目描述​​
• ​​解题思路​​
• ​​源码分享​​
• ​​学习总结​​
• ​​????往期文章----好文推荐????​​

题目描述

​资源限制​

时间限制：2.0s 内存限制：256.0MB

​问题描述​

　　给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。

你能求出数列中总共有多少个K倍区间吗？

​输入格式​

　　第一行包含两个整数N和K。(1 <= N, K <= 100000)

　　以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

​输出格式​

　　输出一个整数，代表K倍区间的数目。

样例输入
5 2
1
2
3
4
5
样例输出
6

解题思路

​方法1：​ 暴力求解法

• 暴力法求解，直接将所有情况的值进行求值，看看是否符合题目要求，不过这种方法肯定是会超时的，接下来把源码分享给大家

import os
import sys

# 请在此输入您的代码
N, K = map(int,input().split())
list1 = []
for i in range(N):
a = int(input())
list1.append(a)
count = 0
for i in range(N):
for j in range(i,N):
a = sum(list1[i:j+1])
if a % K == 0:
count += 1
print(count)

​方法二：​ 数学分析方法

• 首先我们知道 ​( s [ j ] − s [ i − 1 ] ) % k = s [ j ] % k − s [ i − 1 ] % k​ 所以 ​( s [ j ] − s [ i − 1 ] ) % k = 0 就相当于s [ j ] % k − s [ i − 1 ] % k = 0​ 也就是​s [ j ] % k = s [ i − 1 ] % k​

• 所以我们可以直接在列表中存储余数出现的次数

拿题目给的例子说：
前5项的和是15,15%2=1
前两项的和是3,3%2=1
前一项的和是1,1%2=1

• 所以这个取余之后值为1出现了三次，我们不难看出：我们可以取第五个数 - 第一个数、第五个数 - 第二个数、第二个数 - 第一个数这三种结果说白了，就是在出现的次数3里面任选两个，即：C32。
• 所以说，创建一个列表来存储余数，余数的种类一定和除数一样大，因为还包括0在内：​​s = [0]*k​​
• 这里用依次相加余数的方法求解第一项、第一项+第二项、第一项+第二项+第三项…的余数：​​temp_sum.append((temp_sum[i - 1] + int(input())) % k) # 求temp_sum[i]即下一项的值​​
• 不同的余数出现则进行+1：​​s[temp_sum[i]] += 1​​
• 由数学中的组合排列公式进行求值处理，Cnk模式：`res += s[i] * (s[i] - 1) // 2
• 加s[0]的原因是不用做减法，其本身相除后的余数就是0，所以直接加进去就可以啦​​print(res+s[0])​​

源码分享

n, k = map(int, input().split())
s = [0]*k # 创建一个列表来存储余数，余数的种类一定和除数一样大，因为还包括0在内
temp_sum = [0] # 前缀和取余K
for i in range(1, n + 1):
# 这里用依次相加余数的方法求解第一项、第一项+第二项、第一项+第二项+第三项.....的余数
temp_sum.append((temp_sum[i - 1] + int(input())) % k) # 求temp_sum[i]即下一项的值
s[temp_sum[i]] += 1

res = 0
for i in range(len(s)): # 由数学中的组合排列公式进行求值处理，Cnk模式
res += s[i] * (s[i] - 1) // 2

print(res+s[0]) # 加s[0]的原因是不用做减法，其本身相除后的余数就是0，所以直接加进去就可以啦

学习总结

​​????今天是我在Python训练营的第 31 天，希望每天都能见到最棒的你????​​

​​

???????????? 好啦，这就是今天要分享给大家的全部内容了

❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~