#include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> #define MAX 100010 #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b int L[MAX],R[MAX],a[MAX],Index[MAX]; int n,mod=1e9+7; void read(){ int i; for(i=1;i<=n;i++){ scanf("%d",a+i); L[i]=0; R[i]=n+1; } return ; } int main(){ int i,j,temp,sum; while(scanf("%d",&n)!=EOF){ read(); sum=0; memset(Index,-1,sizeof(Index)); for(i=1;i<=n;i++){ temp=sqrt(1.0*a[i]); for(j=1;j<=temp;j++){ if(a[i]%j==0){ if(Index[j]!=-1)L[i]=Max(Index[j],L[i]); if(Index[a[i]/j]!=-1)L[i]=Max(Index[a[i]/j],L[i]); } } Index[a[i]]=i; } memset(Index,-1,sizeof(Index)); for(i=n;i>=1;i--){ temp=sqrt(1.0*a[i]); for(j=1;j<=temp;j++){ if(a[i]%j==0){ if(Index[j]!=-1)R[i]=Min(Index[j],R[i]); if(Index[a[i]/j]!=-1)R[i]=Min(Index[a[i]/j],R[i]); } } Index[a[i]]=i; } for(i=1;i<=n;i++) sum=(sum+(i-L[i])*(R[i]-i)%mod)%mod; printf("%d\n",sum); } return 0; } |
Double click to view unformatted code.