xml地图|网站地图|网站标签 [设为首页] [加入收藏]

hdu_5288_OO’s Sequence

来源:http://www.ccidsi.com 作者:最新解决方案 人气:101 发布时间:2019-09-25
摘要:OO has got a array A of size n ,defined a function f(l,r) represent thenumber of i (l=i=r) , that there's noj(l=j=r,ji) satisfy a i mod a j =0,now OO want to know hdu_5288_OO’s Sequence, OO has got a array A of size n ,defined a functio

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

hdu_5288_OO’s Sequence,

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 ∑i=1n∑j=inf(i,j) mod (109 7).∑i=1n∑j=inf(i,j) mod (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;
    }
}

  

Sequence, 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,ji) satisfy a i mod a j =0,now OO...

∑i=1n∑j=inf(i,j) mod (109 7).∑i=1n∑j=inf(i,j) mod (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

本文由68399皇家赌场发布于最新解决方案,转载请注明出处:hdu_5288_OO’s Sequence

关键词: 68399皇家赌场

最火资讯