View Code of Problem 3571

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define N 100011
int mod=1e9+7;
int a[N],l[N],r[N],n,pre[N],last[N];
void findright(int x)
{
        int i,j;
        for(i=1;i<=n;i++)
        {
                for(j=a[i];j<=10000;j=j+a[i])
                {
                        if(pre[j]!=0&&r[pre[j]]==n+1)
                                r[pre[j]]=i;
                }
                pre[a[i]]=i;
        }
}
void findleft(int x)
{
        int i,j;
        for(i=n;i>=1;i--)
        {
                for(j=a[i];j<=10000;j=j+a[i])
                {
                        if(last[j]!=0&&l[last[j]]==0)
                                l[last[j]]=i;
                }
                last[a[i]]=i;
        }
}
int main()
{
        int i,j;
        long long cnt;
        while(scanf("%d",&n)!=EOF)
        {
                memset(pre,0,sizeof(pre));
                memset(last,0,sizeof(last));
                cnt=0;
                for(i=1;i<=n;i++)
                {
                        r[i]=n+1,l[i]=0;
                        scanf("%d",&a[i]);
                }
                        findleft(i);
                        findright(i);
                for(i=1;i<=n;i++)
                {
                        long long a=(long long)r[i]-i;
                        long long b=(long long)i-l[i];
                        cnt=(cnt+(a*b)%mod)%mod;
                }
                printf("%lld\n",cnt);
        }
        return 0;
}