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

题目描述

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

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

网络异常，图片无法展示

|

网络异常，图片无法展示

|