#include <iostream> #include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" #include <algorithm> using namespace std; const int N=1e9+7; int a[111111],pre[111111],last[111111],l[111111],r[111111]; int main(void) { int n; //freopen("1001.in","r",stdin); while(scanf("%d",&n)!=EOF) { memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(pre,0,sizeof(pre)); memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); l[i]=1; r[i]=n; } for(int i=1;i<=n;i++) { for(int j=a[i];j<=10000;j+=a[i]) if(pre[j]!=0&&r[pre[j]]==n) r[pre[j]]=i-1; pre[a[i]]=i; } for(int i=n;i>0;i--) { for(int j=a[i];j<=10000;j+=a[i]) if(last[j]!=0&&l[last[j]]==1) l[last[j]]=i+1; last[a[i]]=i; } long long int sum=0; for(int i=1;i<=n;i++) sum=sum%N+((i-l[i]+1)%N*(r[i]-i+1)%N)%N; printf("%lld\n",sum); } } |
Double click to view unformatted code.