📢📢📢📣📣📣🌻🌻🌻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 212345样例输出6

解题思路

方法 1： 暴力求解法

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

import osimport sys
# 请在此输入您的代码N, K = map(int,input().split())list1 = []for i in range(N):  a = int(input())  list1.append(a)count = 0for i in range(N):  for j in range(i,N):    a = sum(list1[i:j+1])    if a % K == 0:      count += 1print(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]  # 前缀和取余Kfor 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 = 0for i in range(len(s)):  # 由数学中的组合排列公式进行求值处理，Cnk模式    res += s[i] * (s[i] - 1) // 2
print(res+s[0])  # 加s[0]的原因是不用做减法，其本身相除后的余数就是0，所以直接加进去就可以啦

学习总结

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