Problem Description

OO has got a array A of size n ,defined a function f(l,r) represent the number of i (l<=i<=r) , that there's no j(l<=j<=r,j<>i) satisfy a_i mod a_j=0,now OO want to know

 

Input

There are multiple test cases. Please process till EOF.

In each test case: 

First line: an integer n(n<=10^5) indicating the size of array

Second line:contain n numbers a_i(0<a_i<=10000)

 

Output

For each tests: ouput a line contain a number ans.

 

Sample Input

5

1 2 3 4 5

 

Sample Output

23

 

Author

FZUACM

 

Source

2015 Multi-University Training Contest 1

 

题目大意：

     

       给出一段序列。它的全部非空且里面的元素也为连续的子集中。不存在它能够整除数的元素的个数的和。

解题思路：

      对序列的每一个元素分开考虑，对于每一个元素。往左边找能够找到连续区间长度为a的序列(包含这个元素),往右边可

以找到长度为b的序列(包含这个元素),那么这个元素出现了a*b次,将每一个元素出现的次数相加就能够了。怎样找这个区

间？发现序列元素值就10000。于是能够开个10000的数组。数组记录这个值最后一次出现的位置。然后枚举约数就

就能够了。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int inf=0x7fffffff;

const int maxn=100000+1000;

const int mod=1000000000+7;

int a[maxn];

long long l[maxn];

long long r[maxn];

int h[maxn];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        memset(h,0,sizeof(h));

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

        scanf("%d",&a[i]);

        int cur=inf,te;

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

        {

            cur=inf;

            for(int j=1;j*j<=a[i];j++)

            {

                if(a[i]%j==0)

                {

                    cur=min(cur,i-h[j]);

                    te=a[i]/j;

                    cur=min(cur,i-h[te]);

                }

            }

            l[i]=cur;

            h[a[i]]=i;

        }

        for(int i=1;i<=10500;i++)

        h[i]=n+1;

        for(int i=n;i>0;i--)

        {

            cur=inf;

            for(int j=1;j*j<=a[i];j++)

            {

                if(a[i]%j==0)

                {

                    cur=min(cur,h[j]-i);

                    te=a[i]/j;

                    cur=min(cur,h[te]-i);

                }

            }

            h[a[i]]=i;

            r[i]=cur;

        }

        long long ans=0;

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

        {

            ans=(ans+(l[i]*r[i]))%mod;

        }

        printf("%I64d\n",ans);

    }

    return 0;

}