整数の組 \((l,r)\) \((1\leq l\leq r\leq N)\) が与えられた時に条件をみたすか判定することについて考えます。
正整数 \(X,Y\) について、「\(X\) が \(Y\) の約数である」ことと、「\(Y\) を \(X\) で割った余りが \(0\) である」ことが同値であることに注意すると必要なステップは次の \(2\) つです。

• \(S=A_l+A_{l+1}+\cdots+A_r\) を求める。
• 各 \(l\leq i\leq r\) について、\(S\) を \(A_i\) で割った余りを求める。余りが \(0\) となるような \(i\) が存在したならば \((l,r)\) は条件をみたさない。そうでないならば、条件をみたす。

上記の \(2\) つは、どちらも for 文と基本演算だけで行うことができます。計算量は \(O(N)\) です。

候補となる組 \((l,r)\) の個数は \(\frac{N(N+1)}{2}\) であり、for 文で列挙することができます。それぞれについて判定を行い、条件をみたすものの個数を数えれば良いです。時間計算量は \(O(N^3)\) となり、本問題の制約下で十分高速です。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	int a[50]={};
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			int s=0;
			for(int k=j;k<=i;k++)s+=a[k];
			bool ok=true;
			for(int k=j;k<=i;k++)if(s%a[k]==0)ok=false;
			if(ok)ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Python による実装例:

n=int(input())
a=list(map(int, input().split()))
ans=0

for i in range(n):
    for j in range(i+1):
        s=0
        for k in range(j,i+1):
            s+=a[k]
        flag=True
        for k in range(j,i+1):
            if s%a[k]==0:
                flag=False
        if flag:
            ans+=1

print(ans)