View Code of Problem 3571

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define MAX(a,b) ((a>b)?(a):(b))
#define MIN(a,b) ((a<b)?(a):(b))
#define LL long long
#define N 100005
#define M 10005
#define INF 1<<30
#define MOD 1000000007

int n;
int a[N];
vector<int> fac[M];
vector<int> sit[M];

void init(){
    for(int i=1;i<M;++i){
        for(int j=i;j<M;j+=i){
            fac[j].push_back(i);
        }
    }
}

int main(){
    init();
	while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=10000;i++)
            sit[i].clear();
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            sit[a[i]].push_back(i);
        }
        LL ans=0;
        LL ll,rr;
        int flag;
        for(int i=1;i<=n;++i){
            ll=0,rr=n+1;
            for(int j=0;j<fac[a[i]].size();++j){
                flag=1;
                for(int k=0;k<sit[fac[a[i]][j]].size();++k){
                    if(sit[fac[a[i]][j]][k]<i){
                        ll=MAX(ll,sit[fac[a[i]][j]][k]);
                    }
                    if(sit[fac[a[i]][j]][k]==i)continue;
                    if(sit[fac[a[i]][j]][k]>i){
                        rr=MIN(rr,sit[fac[a[i]][j]][k]);
                        break;
                    }
                }
            }
            ll=i-ll-1;
            rr=rr-i-1;
            ans=(ans+(ll+1)*(rr+1))%MOD;
        }
        printf("%lld\n",(ans)%MOD);
	}

	return 0;
}