/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
1\leq l\leq r\leq N をみたす整数の組 (l,r) であって、
次の条件をみたすものの個数を求めてください。
l\leq i\leq r をみたす任意の整数 i について、A_i は 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 つであるため、6 を出力します。
入力例 2
3 1 1 1
出力例 2
0
Score : 200 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N that satisfy the following condition:
For every integer i satisfying l\leq i\leq r, A_i is not a divisor of A_l+A_{l+1}+\cdots+A_r.
Constraints
- 1 \leq N \leq 50
- 1 \leq A_i \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
5 8 6 10 5 7
Sample Output 1
6
We have A=(8,6,10,5,7).
For example, (l,r)=(1,2) satisfies the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14, and neither A_1=8 nor A_2=6 is a divisor of 14.
On the other hand, (l,r)=(1,3) does not satisfy the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24, and A_1=8 is a divisor of 24.
The pairs that satisfy the condition are (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5), which is six pairs, so output 6.
Sample Input 2
3 1 1 1
Sample Output 2
0