hdu 5288 OO’s Sequence 枚举+二分

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

5 1 2 3 4 5

Sample Output

Author

FZUACM

Source

2015 Multi-University Training Contest 1

题意：函数f(l,r)表示区间l，r中，不是区间中其他所有数的倍数的数的个数

直接暴力显然是不可以的

思路：

1.预处理出1~1e5每一个数的所有因子，O(nsqrt(n))

2.数组l[i],r[i]，分别表示从i开始最左能够到达的位置和最右能够达到的位置，使得[l[i],r[i]]中，i不是任何数的倍数

那么现在就是求出l,r的问题了

pos[i]表示i在数组中出现的位置

对于a[i],我们枚举a[i]的所有因子，对于每一个因子，我们已经知道这个因子在数组中出现的位置，二分，然后更新l[i],r[i]

求出l,r数组后，

对于每一个数a[i],对答案的贡献=(i-l[i]+1)*(r[i]-i+1)

就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define LL long long
#define pb push_back

using namespace std;

const int maxn=1e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;

int a[maxn];
int l[maxn];
int r[maxn];
vector <int> di[maxn];
vector <int> pos[maxn];

void pre_init()
{
    for(int i=1;i<maxn;i++){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                di[i].pb(j);
                if(i/j != j)
                    di[i].pb(i/j);
            }
        }
    }
}

void init(int n)
{
    for(int i=1;i<maxn;i++){
        pos[i].clear();
    }
}

void solve(int );

int main()
{
    pre_init();

    int n;
    while(~scanf("%d",&n)){
        init(n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pos[a[i]].pb(i);
        }
        solve(n);
    }
    return 0;
}

void solve(int n)
{
    for(int i=1;i<=n;i++){
        l[i]=1,r[i]=n;
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<di[a[i]].size();j++){
            int k=di[a[i]][j];

            int left=0,right=pos[k].size()-1;

            if(right<left)
                continue;

            if(pos[k][left]<i){
                while(right-left>1){
                    int mid=(left+right)>>1;
                    if(pos[k][mid]>=i)
                        right=mid;
                    else
                        left=mid;
                }
                if(pos[k][right]<i)
                    l[i]=max(l[i],pos[k][right]+1);
                else
                    l[i]=max(l[i],pos[k][left]+1);
            }


            left=0,right=pos[k].size()-1;
            if(pos[k][right]>i){
                while(right-left>1){
                    int mid=(left+right)>>1;
                    if(pos[k][mid]<=i)
                        left=mid;
                    else
                        right=mid;
                }
                if(pos[k][left]>i)
                    r[i]=min(r[i],pos[k][left]-1);
                else
                    r[i]=min(r[i],pos[k][right]-1);
            }


        }
    }

    /*
    for(int i=1;i<=n;i++)
        printf("%d %d
",l[i],r[i]);
    */

    LL ret=0;
    for(int i=1;i<=n;i++){
        ret+=(i-l[i]+1)*(r[i]-i+1)%mod;
        ret=(ret+mod)%mod;
    }


    printf("%I64d
",ret);
    return ;
}