View Code of Problem 3571

#include<stdio.h>
#include<string.h>

#define mod 1000000007
#define MAX 100001

int a[MAX];
int l[MAX],r[MAX];
int index[MAX];

int main(){
	int n;
	long long sum;
	while(scanf("%d", &n)!=EOF){
		sum = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			l[i] = 1, r[i] = n;
		}
		memset(index, 0, sizeof(index));
		for(int i = 1; i <= n; i++){
			for(int j = a[i];j <= 10000; j += a[i])
				if(index[j] && r[index[j]] == n)
					r[index[j]] = i - 1;
			index[a[i]] = i;
		}
		memset(index, 0, sizeof(index));
		for(int i = n; i > 0; i--){
			for(int j = a[i]; j <= 10000; j += a[i])
				if(index[j] && l[index[j]] == 1)
					l[index[j]] = i + 1;
			index[a[i]] = i;
		}
		for(int i = 1; i <= n; i++)
			sum=(sum + ((i - l[i] + 1)*(r[i] - i + 1) % mod)) % mod;
		printf("%lld\n", sum);
	}
	return 0;
}