题目内容

$n$ 个魔法石围成一个环形（即第 $n$ 个魔法石与第 $1$ 个魔法石相邻），每个魔法石蕴含一定的能量值（整数，可正可负）。法师需要选择一段连续的魔法石（至少选择 $1$ 个，可以跨越首尾），收集它们的能量，要求收集的总能量能被 $k$ 整除，且总能量值尽可能大。

请计算满足条件的最大总能量值。如果无法找到任何满足条件的收集方案（即不存在能被 $k$ 整除的连续子数组和），则输出数字 $0$。

输入描述

• $int[]$ $nums$ $n$ 个整数，表示每个魔法石的能量值（按顺时针顺序）

• $int$ $n$ 魔法石数量

• $int$ $k$ 除数

输出描述

一个整数，表示能被 $k$ 整除的最大总能量值；如果不存在，输出数字 $0$。

数据范围

1. $1 \le n \le 2 \times 10^5$

2. $1 \le k \le 1000$

3. $-10^6 \le$ 能量值 $\le 10^6$

要求

• 时间复杂度: $O(n)$ 或 $O(n \log n)$ • 空间复杂度: $O(n)$（允许使用哈希表等辅助数据结构）

样例1

输入

[1,2,3,4,5],5,3

输出

15

说明

选择全部 $5$ 个魔法石，总和为 $15$，能被 $3$整除，且这是所有能被 $3$ 整除的连续子数组和中最大的（如 $3、6、9、12$ 等都小于 $15$）

样例2

输入

[3,-1,2,4,-2,5],6,4

输出

12

说明

选择 $[3, -1, 2, 4, -2, 5]$ 总和为 $11$；

选择 $[4, -2, 5, 3]$ 和为 $10$；

选择 $[2, 4, -2, 5, 3]$ 和为 $12$，能被 $4$ 整除，且为最大值