题面描述

小塔玩一个游戏。

系统发 $1+n$ 张牌，每张牌上有一个整数。

• 第一张牌给小塔，数字为 $m$。
• 后 $n$ 张牌按照发牌顺序排成连续的一行，数字分别为 $a_1, a_2, \ldots, a_n$。

小塔需要判断，在后 $n$ 张牌中，是否存在连续的若干张牌，其和可以被小塔手中牌上的数字 $m$ 整除。

解题思路

要判断在后 $n$ 张牌中是否存在一个连续的子序列，其和可以被小塔手中的数字 $m$ 整除。考虑到：

1. 前缀和与模运算：

   • 计算前缀和数组 prefix_sum，其中 prefix_sum[i] 表示前 $i$ 张牌的总和。
   • 对每个前缀和取模 $m$，即 prefix_sum[i] % m。
   • 如果存在两个前缀和 prefix_sum[i] 和 prefix_sum[j] 满足 prefix_sum[i] % m == prefix_sum[j] % m，且 $i < j$，则子序列从 $i+1$ 到 $j$ 的和可以被 $m$ 整除。

2. 使用哈希表记录模值：

   • 使用一个哈希表（或数组）来记录每个模值首次出现的位置。
   • 遍历前缀和的模值，如果当前模值已经存在于哈希表中，则说明存在满足条件的子序列，输出 1。
   • 如果遍历完所有前缀和后都未找到满足条件的子序列，输出 0。

3. 边界情况处理：

   • 如果某个前缀和本身就可以被 $m$ 整除，即 prefix_sum[i] % m == 0，则从第 $1$ 张牌到第 $i$ 张牌的和可以被 $m$ 整除。

4. 时间与空间复杂度：

   • 每组测试用例的时间复杂度为 $O(n)$，适合 $n \leq 1000$ 和测试用例数不超过 $1000$ 的情况。
   • 使用数组记录模值时，空间复杂度为 $O(m)$，但由于 $m$ 可能较大（$400000$），可考虑使用哈希表以节省空间。

cpp

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    while(cin >> n >> m){
        vector<long long> cards(n);
        for(int i=0; i<n; ++i){
            cin >> cards[i];
        }
        // 使用哈希表记录前缀和的模值是否出现过
        unordered_set<long long> seen;
        long long prefix = 0;
        bool found = false;
        seen.insert(0); // 处理子序列从第一张开始的情况
        for(int i=0; i<n; ++i){
            prefix += cards[i];
            long long mod = prefix % m;
            // 如果当前模值已经出现过，说明存在子序列
            if(seen.find(mod) != seen.end()){
                found = true;
                break;
            }
            seen.insert(mod);
        }
        if(found){
            cout << "1\n";
        }
        else{
            cout << "0\n";
        }
    }
    return 0;
}

python

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().splitlines()
    
    results = []
    index = 0
    while index < len(data):
        # 读取 n 和 m
        n, m = map(int, data[index].split())
        index += 1
        
        # 读取后续 n 张牌的数字
        cards = list(map(int, data[index].split()))
        index += 1
        
        # 使用集合记录前缀和的模值
        seen = set()
        prefix = 0
        found = False
        seen.add(0)  # 处理子序列从第一张开始的情况
        
        for i in range(n):
            prefix += cards[i]
            mod = prefix % m
            
            # 如果当前模值已经出现过，说明存在子序列
            if mod in seen:
                found = True
                break
            
            seen.add(mod)
        
        if found:
            results.append("1")
        else:
            results.append("0")
    
    # 输出所有结果
    print("\n".join(results))

if __name__ == "__main__":
    main()

java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入直到没有更多行
        while (sc.hasNextLine()) {
            // 读取第一行，提取 n 和 m 的值
            int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            // 读取第二行，提取后续 n 张牌的数字
            int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            // 调用 isExist 方法判断是否存在满足条件的子序列，输出结果
            System.out.println(isExist(nums, tmp[1]));
        }
    }

    // 判断在 nums 数组中是否存在连续子序列的和可以被 m 整除
    public static int isExist(int[] nums, int m) {
        HashSet<Integer> remain = new HashSet<>(); // 用于存储模值
        remain.add(0); // 初始化时添加模值 0，以处理子序列从开头开始的情况

        int sum = 0; // 前缀和
        // 遍历每张牌
        for (int num : nums) {
            sum += num; // 更新前缀和
            // 检查当前前缀和的模值是否已存在
            if (remain.contains(sum % m)) {
                return 1; // 如果存在，返回 1
            } else {
                // 否则，将当前模值添加到集合中
                remain.add(sum % m);
            }
        }

        return 0; // 如果遍历结束后没有找到，返回 0
    }
}

题目内容

小红玩一个游戏。

系统发 $1+n$ 张牌，每张牌上有一个整数。

第一张给小红，后 $n$ 张按照发牌顺序排成连续的一行。

需要小红判断，后 $n$ 张牌中，是否存在连续的若干张牌，其和可以整除小红手中牌上的数字。

输入描述

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

第一行有两个整数 $n$ 和 $m$ ，空格隔开。$m$ 代表发给小红牌上的数字。

第二行有 $n$ 个数，代表后续发的 $n$ 张牌上的数字，以空格隔开。

输出描述

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

备注

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

样例1

输入

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

输出

1
0

说明

两组输入。第一组小红牌的数字为 $7$ ，再发了 $6$ 张牌。第 $1、2$ 两张牌数字和为 $14$ ，可以整除 $7$，输出 $1$，第二组小明牌的教字为 $11$，再发了 $10$ 张牌，这 $10$ 张牌数字和为 $10$ ，无法整除 $11$ ，输出 $0$ 。