View Code of Problem 3571

#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.


Back to problem 3571