View Code of Problem 3571

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

#define Max 100010

const int mod  = 1e9+7;
int a[Max];
int L[Max],R[Max];
int index[Max];

int main()
{
    int n;
    while(~scanf("%d",&n)){
        int i;
        for(i=1;i<=n;i++)
            scanf("%d",a+i);
        memset(index,-1,sizeof(index));
        for(i=1;i<=n;i++){
            int temp = sqrt(1.0*a[i]);
            int l=0,j;
            for(j=1;j<=temp;j++){
                if(a[i]%j==0){
                    if(index[j]!=-1)
                        l = index[j]>l?index[j]:l;
                    if(index[a[i]/j]!=-1)
                        l = index[a[i]/j]>l?index[a[i]/j]:l;
                }
            }
            index[a[i]] = i;
            L[i] = l;
        }

        memset(index,-1,sizeof(index));
        for(i=n;i>=1;i--){
            int temp = sqrt(1.0*a[i]);
            int r = n+1;
            int j;
            for(j=1;j<=temp;j++){
                if(a[i]%j==0){
                    if(index[j]!=-1)
                        r = index[j]>r?r:index[j];
                    if(index[a[i]/j]!=-1)
                        r = index[a[i]/j]>r?r:index[a[i]/j];
                }
            }
            index[a[i]] = i;
            R[i] = r;
        }
        int sum=0;
        for(i=1;i<=n;i++)
            sum = (((i-L[i])*(R[i]-i)%mod)+sum)%mod;
        printf("%d\n",sum);
    }
    //printf("Hello world!\n");
    return 0;
}