View Code of Problem 3571

#include<stdio.h>
#include<string.h>
#include<math.h>
#define mod 1000000007
#define MAX 100001
int a[MAX];
int l[MAX],r[MAX];//左右最近因子的下标
int index[MAX];//记录a数组中每个值的下标,如:x=a[i],index[x]=i
int main()
{
	int n,i,j;
	long long sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			l[i]=1,r[i]=n;
		}
		memset(index,0,sizeof(index));
		for(i=1;i<=n;i++)//从左往右找,所以a数组下标录入index也是从ai~an
		{   //因为上面for循环,所以当i=x时,对ax而言,如果它的倍数存在,那么一定在它前面(ay且0<y<x),即ax是ay的因子(最近右因子)
			for(j=a[i];j<=10000;j+=a[i])//a数组中任意值都是满足小于10000
				if(index[j]!=0&&r[index[j]]==n)//如果已经出现并且在右边最近的因子还没有找到,如果已找到那么找到的那个已经是最近不用更新
					r[index[j]]=i-1;
			index[a[i]]=i;//记录a数组中某一值的下标
		}
		memset(index,0,sizeof(index));
		for(i=n;i>0;i--)//和上面同理,这里从右向左走找左因子
		{
			for(j=a[i];j<=10000;j+=a[i])
				if(index[j]!=0&&l[index[j]]==1)//如果已经出现并且在左边最近的因子还没有找到
					l[index[j]]=i+1;
			index[a[i]]=i;
		}
		for(i=1;i<=n;i++)
			sum=(sum+((i-l[i]+1)*(r[i]-i+1)%mod))%mod;
		printf("%lld\n",sum);
	}
	return 0;
}