← 返回题目列表

AtCoder · abc435_b

D. 不可整除的范围

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

给你一个正整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
查找整数对的数量 (l,r) 满意 1\leq l\leq r\leq N 满足以下条件:

对于每个整数 i 满意 l\leq i\leq r, A_i is 不 的除数 A_l+A_{l+1}+\cdots+A_r.

约束

  • 1 \leq N \leq 50
  • 1 \leq A_i \leq 1000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

输出答案。


示例输入 1

5
8 6 10 5 7

示例输出 1

6

我们有 A=(8,6,10,5,7).

例如, (l,r)=(1,2) 满足条件,因为 A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14,也不 A_1=8 也不 A_2=6 是除数 14.
另一方面, (l,r)=(1,3) 不满足条件,因为 A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24,和 A_1=8 是除数 24.

满足条件的对是 (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5),这是六对,所以输出 6.


示例输入 2

3
1 1 1

示例输出 2

0