#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; } |
Double click to view unformatted code.