HDU 5288——OO’s Sequence——————【技巧题】

OO’s Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1549 Accepted Submission(s): 559

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

\sum i = 1 n \sum j = i n f (i, j) m o d （ 10 9 + 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 a_i(0<a_i<=10000)

Output

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

Sample Input

1 2 3 4 5

Sample Output

题目大意：给你一个长度为n的区间。求这个区间内任意子区间中ai没有因子的ai的个数。

解题思路：从左往右遍历a数组得到L数组。对于ai，枚举j 1-->sqrt（ai），如果j是ai的约数并且j已经在ai之前，那么我用max取离i最近的位置；相应的ai/j也是ai的约数，同理如果ai/j也在ai之前，也用max取离i最近的位置。对于R数组，同理可得。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=1e5+20;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int a[maxn],L[maxn],R[maxn];
int pos[maxn];
int main(){
    int n,limj;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        memset(pos,0,sizeof(pos));
        for(int i=1;i<=n;i++){
            L[i]=0;
            limj=(int)sqrt(a[i]);
            for(int j=1;j<=limj;j++){
                if(a[i]%j==0){
                    if(pos[j]){
                        L[i]=max(L[i],pos[j]);
                    }
                    if(pos[a[i]/j]){
                        L[i]=max(L[i],pos[a[i]/j]);
                    }
                }
            }
            pos[a[i]]=i;
        }
        memset(pos,0,sizeof(pos));
        for(int i=n;i>=1;i--){
            R[i]=n+1;
            limj=(int)sqrt(a[i]);
            for(int j=1;j<=limj;j++){
                if(a[i]%j==0){
                    if(pos[j]){
                        R[i]=min(R[i],pos[j]);
                    }
                    if(pos[a[i]/j]){
                        R[i]=min(R[i],pos[a[i]/j]);
                    }
                }
            }
            pos[a[i]]=i;
        }
        int sum=0,res;
        for(int i=1;i<=n;i++){
            sum=(sum%MOD+((i-L[i])*(R[i]-i))%MOD)%MOD;
        }
        printf("%d
",sum);
    }
    return 0;
}