题目内容

塔子哥是一个喜欢玩扑克牌的人，他经常和朋友们一起玩各种有趣的扑克牌游戏。他最近学会了一个新的游戏，叫做“整除游戏”。这个游戏的规则是这样的：

系统会随机发 $n+1$ 张牌，每张牌上都有一个正整数，不一定是扑克牌上的数字。第一张牌给塔子哥，后 $n$ 张牌按照发牌顺序排成连续的一行，让塔子哥看到。然后，系统会问塔子哥一个问题：后 $n$ 张牌中，是否存在连续的若干张牌，其和可以整除塔子哥手中牌上的数字？塔子哥需要回答 1 或者 0 ，表示是或者否。

思路:取模

由小学数学，我们知道数组中一个子段$[l,r]$是$m$的倍数 , 当且仅当 $(a_l + ... + a_r) \% m = 0$

那么将其转化成前缀和的形式，就是$(s_r - s_{l-1}) \% m = 0$

也就是$s_l \% mod = s_r \% mod$

所以我们求一下前缀和，看有没有$i,j , i \neq j$ 使得$s_i = s_j$ 的。有输出1,没有输出0