OO’s Sequence

题目连接：

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 ai mod aj=0,now OO want to know

∑i=1n∑j=inf(i,j) mod （109+7）.

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 ai(0<ai<=10000)

Output

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

Sample Input

5

1 2 3 4 5

Sample Output

23

Hint

题意

f(l,r)表示[l,r]区间中有多少个i满足在这个区间中找不到其他j使得ai%aj=0

然后让你输出所有f(l,r)的累加。

题解：

对于每一个位置，我算贡献就好了。

直接暴力分解a[i]就好了。

复杂度nsqrtn的。

代码

#include
    
     using namespace std;const int maxn = 1e5+6;const int mod = 1e9+7;int a[maxn],n;int L[maxn],R[maxn];int p[maxn];int main(){    while(scanf("%d",&n)!=EOF)    {        memset(L,0,sizeof(L));        memset(R,0,sizeof(R));        memset(p,0,sizeof(p));        memset(a,0,sizeof(a));        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        for(int i=1;i<=n;i++)        {            for(int j=1;j<=sqrt(a[i]);j++)                if(a[i]%j==0)L[i]=max(L[i],p[j]+1),L[i]=max(L[i],p[a[i]/j]+1);            p[a[i]]=i;        }        reverse(a+1,a+1+n);        memset(p,0,sizeof(p));        for(int i=1;i<=n;i++)        {            for(int j=1;j<=sqrt(a[i]);j++)                if(a[i]%j==0)R[i]=max(R[i],p[j]+1),R[i]=max(R[i],p[a[i]/j]+1);            p[a[i]]=i;        }        long long ans = 0;        for(int i=1;i<=n;i++)        {            ans += 1ll*(i-L[i]+1)*(n-R[n-i+1]+1-i+1);            ans%=mod;            //cout<
     
      <<" "<
      
       <