View Code of Problem 3571

#include <stdio.h>
#include <stdlib.h>

#define Max 100010
#define limit 1000000007

int left[Max];
int right[Max];
int a[Max];

void research(int t,int n){
    int i,j;
    for(i=t-1;i>=1;i--)
        if(a[t]%a[i]==0)
            break;
    left[t] = i;
    for(j=t+1;j<=n;j++)
        if(a[t]%a[j]==0)
            break;
    right[t] = j;
}

int main()
{
    int n;
    while(~scanf("%d",&n)){
        int i;
        long long sum=0;
        for(i=1;i<=n;i++)
            scanf("%d",a+i);
        for(i=1;i<=n;i++)
            research(i,n);
        for(i=1;i<=n;i++){
            sum += (right[i]-i)*(i-left[i]);
            sum %= limit;
        }
        printf("%lld\n",sum);
        //printf("%d\n",right[1]);
    }
    //printf("Hello world!\n");
    return 0;
}

Double click to view unformatted code.


Back to problem 3571