#LQB0068. 能被k整除的子数列

能被k整除的子数列

题目描述: 给定包含 n 个整数的数列,从中选取一段连续子数列,使其元素之和能被 k 整除。 请找出符合要求的最长连续子数列并输出其长度以及子数列本身; 如果符合要求的最长连续子数列有多个,则输出起始位置最靠后的那个子数列。如果不存在符合要求的子数列,则输出 -1。

例如:n = 7,k = 7,数列为 7、3、4、1、5、14、9; 连续子数列 {7} 、{7,3,4} 、{3,4}、和 {5,14,9} 的和都能被 7 整除; 其中最长的连续子数列有 {7,3,4} 和 {5,14,9},起始位置最靠后的是 {5,14,9}。 故符合要求的最长连续子数列长度为 3,子数列为 5 14 9。

输入描述:

第一行输入两个整数 n 和 k(1≤n≤105,2≤k≤108),整数之间以一个空格隔开第二行输入 n 个整数(1≤整数≤104),整数之间以一个空格隔开

输出描述:

如果存在符合要求的最长连续子数列,则输出为两行第一行输出一个整数,表示最长连续子数列的长度第二行输出若干个整数,表示起始位置最靠后的最长连续子数列,整数之间以一个空格隔开如果不存在,则输出 -1。

7 7
7 3 4 1 5 14 
3
5 14 9

Limitation

1s, 1024KiB for each test case.