预处理出每一个数字的左右两边能够整除它的近期的数的位置

OO’s Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1880    Accepted Submission(s): 672

5

1 2 3 4 5

23

/* ***********************************************

Author        :CKboss

Created Time  :2015年07月24日 星期五 08时12分15秒

File Name     :HDOJ5288.cpp

************************************************ */

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstdlib>

#include <vector>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long int LL;

const int maxn=100100;

const LL MOD=(LL)(1e9+7);

int n;

int a[maxn];

int Left[maxn],Right[maxn];

vector<int> pos[10010];

void init()

{

	for(int i=0;i<=10010;i++)

	{

		pos[i].clear();

	}

	for(int i=0;i<n;i++)

	{

		Left[i]=0; Right[i]=n-1;

	}

}

void pre()

{

	for(int i=0;i<n;i++)

	{

		int x=a[i];

		for(int j=x;j<=10000;j+=x)

		{

			for(int k=0,sz=pos[j].size();k<sz;k++)

			{

				int z=pos[j][k];

				if(z==i) continue;

				else if(z<i)

				{

					Right[z]=min(Right[z],i-1);

				}

				else if(z>i)

				{

					Left[z]=max(Left[z],i+1);

				}

			}

		}

	}

}

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	while(scanf("%d",&n)!=EOF)

	{

		init();

		for(int i=0;i<n;i++)

		{

			scanf("%d",a+i);

			pos[a[i]].push_back(i);

		}

		pre();

		LL ans=0;

		for(int i=0;i<n;i++)

		{

			LL L=i-Left[i]+1LL;

			LL R=Right[i]-i+1LL;

			ans=(ans+(L*R)%MOD)%MOD;

		}

		cout<<ans<<endl;

	}

    return 0;

}