小明正在尝试一种新的牌游戏。游戏规则只如下:首先，小明拿到一张写有数字m的牌。 然后，他会拿到另外n张牌，上面分别写有不同的数字，牌排成一排。小明的目标是从这排牌中找到一串连续的牌，这些牌上数字的总和可以被 m整除。你的任务是判断小明是否可以完成这个目标。
输入描述
第一行包含两个整数:n和 m。其中n是小明拿到的牌的数量(不包括写有 m 的牌)，m 是写在第一张牌上的数字。第二行包含 n个整数，这些整数分别是n张牌上的数字，
输出描述
如果小明可以找到一个连续的牌串，这些牌上数字的和可以被 m 整除，输出“1"。如果找不到符合条件的牌串，输出"0”。
示例1
输入：
6 7
2 12 6 3 5 5
输出：
1
示例2
输入：
10 11
1 1 1 1 1 1 1 1 1 1
输出：
0
问题分析
需要判断是否存在一个连续子数组，其元素之和能被给定的整数m整除。关键在于利用前缀和和模运算的性质来高效解决问题。
解题思路
- 前缀和与模运算：计算前缀和数组
prefix，其中prefix[i]表示前i个元素的和。若存在prefix[j] % m == prefix[i] % m（其中j > i），则子数组[i+1, j]的和能被m整除。 - 哈希表优化：使用哈希表记录前缀和模
m的结果首次出现的位置。若同一余数再次出现，说明存在满足条件的子数组。
实现代码
Java
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } Map<Integer, Integer> modMap = new HashMap<>(); modMap.put(0, -1); int prefixMod = 0; boolean found = false; for (int i = 0; i < n; i++) { prefixMod = (prefixMod + nums[i]) % m; if (modMap.containsKey(prefixMod)) { found = true; break; } modMap.put(prefixMod, i); } System.out.println(found ? "1" : "0"); } }Python
n, m = map(int, input().split()) nums = list(map(int, input().split())) mod_map = {0: -1} prefix_mod = 0 found = False for i in range(n): prefix_mod = (prefix_mod + nums[i]) % m if prefix_mod in mod_map: found = True break mod_map[prefix_mod] = i print(1 if found else 0)JavaScript
const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = []; rl.on('line', (line) => { input.push(line); }).on('close', () => { const [n, m] = input[0].split(' ').map(Number); const nums = input[1].split(' ').map(Number); const modMap = new Map(); modMap.set(0, -1); let prefixMod = 0; let found = false; for (let i = 0; i < n; i++) { prefixMod = (prefixMod + nums[i]) % m; if (modMap.has(prefixMod)) { found = true; break; } modMap.set(prefixMod, i); } console.log(found ? "1" : "0"); });C++
#include <iostream> #include <unordered_map> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } unordered_map<int, int> modMap; modMap[0] = -1; int prefixMod = 0; bool found = false; for (int i = 0; i < n; i++) { prefixMod = (prefixMod + nums[i]) % m; if (modMap.find(prefixMod) != modMap.end()) { found = true; break; } modMap[prefixMod] = i; } cout << (found ? "1" : "0") << endl; return 0; }代码说明
- 输入处理：读取输入的
n、m和数组nums。 - 哈希表初始化：初始化哈希表
modMap并预存0: -1，表示前缀和为0的虚拟位置。 - 遍历数组：计算前缀和的模
m结果，检查是否已存在于哈希表中。若存在则直接返回1，否则记录当前余数的位置。 - 输出结果：根据是否找到满足条件的子数组输出
1或0。
这种方法的时间复杂度为O(n)，空间复杂度为O(min(n, m))，适用于大规模数据。
