E-数字游戏-(200p)

数字游戏

问题描述

小明正在玩一个数字游戏。系统会发放 张牌，每张牌上都有一个整数。第一张牌给小明，后续 张牌按发牌顺序排成一行。小明需要判断，在后 张牌中，是否存在连续的若干张牌，其和可以被小明手中牌上的数字整除。

输入格式

输入数据包含多组，每组输入数据有两行，直到文件结尾。

第一行包含两个整数 和 ，用空格分隔。 表示发给小明牌上的数字。

第二行包含 个整数，表示后续发的 张牌上的数字，以空格分隔。

输出格式

对每组输入，如果存在满足条件的连续若干张牌，则输出 1；否则，输出 0。

样例输入

6 7
2 12 6 3 5 5
10 11
1 1 1 1 1 1 1 1 1 1

样例输出

1
0

样例解释

数据范围

• 
• 牌上的整数
• 输入的组数不多于 1000
• 用例确保输入都正确，不需要考虑非法情况。

题解

前缀和+数学

这道题目的核心在于如何高效地判断是否存在连续的若干张牌，其和可以被小明手中的牌整除。乍看之下，可能会想到暴力枚举所有可能的连续子序列，但这种方法的时间复杂度是 ，对于大规模数据会超时。

实际上，这个问题可以通过前缀和和数学性质来解决：

1. 首先，计算前缀和数组。前缀和数组的第 i 个元素表示前 i 张牌的和。

2. 利用数学性质：如果两个数 a 和 b 的差能被 k 整除，那么 a 和 b 除以 k 的余数相同。

3. 遍历前缀和数组，对每个元素求其除以 m（小明手中的牌）的余数。

4. 如果出现了相同的余数，说明存在一段连续的牌，其和可以被 m 整除。

举个例子： 假设小明的牌是 7，后续的牌是 [2, 12, 6, 3, 5, 5]。 前缀和数组是 [0, 2, 14, 20, 23, 28, 33]。 对每个元素除以 7 取余：[0, 2, 0, 6, 2, 0, 5]。

可以看到，有多个 0 出现，这意味着存在和可以被 7 整除的连续子序列。

这种方法的时间复杂度是 ，空间复杂度也是 。对于给定的数据范围（，组数不超过 1000），这个解法是完全可以接受的。

参考代码

• Python

def check_divisible_subsequence(n, m, cards):
    """
    检查是否存在连续的若干张牌，其和可以被m整除
    
    :param n: 牌的数量
    :param m: 小明手中牌的数字
    :param cards: 后续发的n张牌上的数字列表
    :return: 如果存在满足条件的连续若干张牌，返回1；否则返回0
    """
    # 计算前缀和
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i-1] + cards[i-1]
    
    # 用集合记录出现过的余数
    remainders = set()
    
    for sum_val in prefix_sum:
        remainder = sum_val % m
        if remainder in remainders:
            return 1
        remainders.add(remainder)
    
    return 0

# 主函数，处理输入和输出
def main():
    while True:
        try:
            # 读取输入
            n, m = map(int, input().split())
            cards = list(map(int, input().split()))
            
            # 检查并输出结果
            result = check_divisible_subsequence(n, m, cards)
            print(result)
        except EOFError:
            break

if __name__ == "__main__":
    main()

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1001

int check_divisible_subsequence(int n, int m, int* cards) {
    // 计算前缀和
    long long prefix_sum[MAX_N] = {0};
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i-1] + cards[i-1];
    }
    
    // 用数组记录出现过的余数
    int remainders[MAX_N] = {0};
    
    for (int i = 0; i <= n; i++) {
        int remainder = prefix_sum[i] % m;
        if (remainders[remainder]) {
            return 1;
        }