15-4连续子串和的整除问题

问题描述

小M是一个五年级的小学生，今天他学习了整除的知识，想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1}，然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这个问题吗？

测试样例

样例1：

输入：n = 3,b = 3,sequence = [1, 2, 3]
输出：3

样例2：

输入：n = 4,b = 5,sequence = [5, 10, 15, 20]
输出：10

样例3：

输入：n = 5,b = 2,sequence = [1, 2, 3, 4, 5]
输出：6

def solution(n, b, sequence):count = 0  # 用于记录符合条件的子序列数量# 外层循环，确定子序列的起始位置for start in range(n):current_sum = 0  # 当前子序列的和# 内层循环，确定子序列的结束位置for end in range(start, n):current_sum += sequence[end]  # 更新当前子序列的和# 检查当前和是否能被 b 整除if current_sum % b == 0:count += 1  # 如果可以整除，则计数加一return count  # 返回符合条件的子序列数量if __name__ == "__main__":# 测试样例sequence1 = [1, 2, 3]print(solution(3, 3, sequence1) == 3)  # 输出: Truesequence2 = [5, 10, 15, 20]print(solution(4, 5, sequence2) == 10)  # 输出: Truesequence3 = [1, 2, 3, 4, 5]print(solution(5, 2, sequence3) == 6)  # 输出: True# 其他测试用例sequence4 = [1, 1, 1, 1]print(solution(4, 2, sequence4) == 10)  # 输出: True (所有子序列的和都是 1 或 2 的倍数)