📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜
🏅🏅🏅2021年度博客之星TOP100,2021年度博客之星领域TOP5，Python领域优质创作者，欢迎大家找我合作学习（文末有VX 想进学习交流群or学习资料 欢迎+++）
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

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

@TOC

题目描述

资源限制
时间限制：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 天，希望每天都能见到最棒的你🏅

🌲🌲🌲 好啦，这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~