OO’s Sequence

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

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 （ 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 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 定义 f(l , r) 表示对于 i (l=<i<=r) 不存在 j (l<=j<=r &&j!=i) 使得 A[i]%A[j]==0的i的个数

求所有l,r (1<=l<=n && 1<=r<=n l<=r)的f（l,r）的和

题目思路：

首先这题如果暴力的话肯定超时，所以我们可以从这个暴力想，，中间有很多其实没有必要计算的，

也就是说重复计算了很多，然后我们来考虑 a[i]%a[j]==0 即a[j] 为a[i]的约数

而对于a[i] 这个数我们想他存在于多少个区间里都是有效的，而由上一条推论我们可以预先算出a[i] 的约数，

然后有了这个我们就可以从a[i]向左右扩展，所以我们定义 l[i] r[i] 表示 a[i] 向左向右可以扩展多少，最后我们就可以

算出对于a[i] 他存在的有效区间的个数，因为a[i] <=1e4 所以我们可以预处理所有的数，这里我们用到类似线性筛的思想

在接近线性的时间预处理

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define mod 1000000007
const int maxn = 1e5+100;
int l[maxn],r[maxn],a[maxn],pos[maxn];
vector<int>G[10005];
int main()
{
    for(int i=1;i<=10000;i++)
    {
        for(int j=i;j<=10000;j+=i)
        {

            G[j].push_back(i);    //预处理所有约数
        }
    }

    int n;

    while(~scanf("%d",&n))
    {
        memset(pos,0,sizeof(pos));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),l[i]=1,r[i]=n;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<G[a[i]].size();j++)
            {
                int v = G[a[i]][j];
                l[i] = max(l[i],pos[v]+1);
            }
            pos[a[i]] = i;
        }
        memset(pos,0,sizeof(pos));
        for(int i=n;i>=1;i--)
        {
            for(int j=0;j<G[a[i]].size();j++)
            {
                int v = G[a[i]][j];
                if(!pos[v])continue;
                r[i] = min(r[i],pos[v]-1);
            }
            pos[a[i]] = i;
        }
        long long ans = 0;
        for(int i=1;i<=n;i++)
        {
            ans+=(long long)(i-l[i]+1)*(r[i]-i+1);
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

HDU5288

OO’s Sequence