首页 > > 程序设计 > C/C++ >

hdu_5288_OO’s Sequence

2018-06-17 21:32:34来源：未知阅读 ()

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 ） .

InputThere 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)
OutputFor each tests: ouput a line contain a number ans.Sample Input

5
1 2 3 4 5

Sample Output

23

这道题目很难，不光是题意。
求不能被所有aj整除的ai有几个。规律还是比较好找的，难点在于数据大，二维暴力不存在的。
举上述例子，
11. 12  13  14  15
21. 22. 23  24  25
31. 32  33. 34  35
41. 42. 43  44. 45
51. 52  53  54  55.
有点的可以被整除。不能暴力想到以ai==aj为分界枚举左右区间
发现1*5+1*4+2+3+2*2+4*1
左区间的最大值乘以右区间最大值,左右区间的算法实在完蛋，看了题解找边界的算法懂了。

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define mod 1000000007
ll a[100005];
ll l[100005];
ll r[100005];
ll pos[100005];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(pos,0,sizeof(pos));
        for(ll i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            r[i]=n+1;
        }
        for(ll i=1;i<=n;i++)
        {
            for(ll j=1;j*j<=a[i];j++)
            {
                if(a[i]%j==0)
                    l[i]=max(l[i],max(pos[j],pos[a[i]/j]));
            }
            pos[a[i]]=i;
        }
        for(ll i=1;i<=10000;i++)
            pos[i]=n+1;
        for(ll i=n;i>0;i--)
        {
            for(ll j=1;j*j<=a[i];j++)
            {
                if(a[i]%j==0)
                    {r[i]=min(r[i],min(pos[j],pos[a[i]/j]));
                    //cout<<r[i]<<endl;
                    }
            }
            pos[a[i]]=i;
        }
        ll ans=0;
        //l[1]=0;
       /* for(ll i=1;i<=n;i++)
        {
            //cout<<i-l[i]<<endl,cout<<r[i]-i+1<<endl;
        }*/
        for(ll i=1;i<=n;i++)
        {
            ans=(ans+((i-l[i])*(r[i]-i)))%mod;
        }
        cout<<ans<<endl;
    }
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有