小 S 设计了一道题目,准备作为礼物送给大家。
给定一个长度为 n 的整数序列 a1,a2,⋯,an。
输出它的任意一个满足以下要求的非空子序列 ab1,ab2,⋯,abk:
(i=1∑kabi)modn=0
可以证明,这样的子序列一定存在。
小 L 看完题目后,向大家解释了一些基本概念:
任取整数 k 满足 1≤k≤n,以及 k 个整数 b1,b2,⋯,bk 满足
1≤b1<b2<⋯<bk≤n
则称 ab1,ab2,⋯,abk 是 a1,a2,⋯,an 的一个非空子序列。
关于求和号 ∑,它的含义是
i=1∑kabi=ab1+ab2+⋯+abk
在这里,mod 运算的定义是
xmody=x−⌊yx⌋y
其中 ⌊z⌋ 表示 ≤z 的最大整数。xmody=0 等价于 x 是 y 的倍数。