HDU 5288 OO’s Sequence [数学]

HDU 5288 OO’s Sequence

http://acm.hdu.edu.cn/showproblem.php?pid=5288
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）.

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

这题的题意是后来看了题解才懂的，意思是给定一个序列，对于每一个数，包括这个数的区间里的其他的数都不是这个数的因数，求对于每一个数的区间的个数的总和。
也就是说对于任何一个数，往左找到第一个它的因数的位置记作l，往右找到它的第一个因数的位置记作r，那么这个数对应的区间的个数是(i-l)*(r-i)，然后对所有的数求一个和就可以了。
因为这里数的范围只有1e4，所以一开始预处理1e4以内的数的因数存在vector[N]里。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <string>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#include <map>

#define INF 0x3f3f3f3f

#define lowbit(x) (x&(-x))

using namespace std;

typedef long long ll;

const int maxn = 1e5+;

const int N = 1e4+;

const int mol = 1e9+;

int arr[maxn],l[maxn],r[maxn],vis[N];

vector <int> vi[N];

int main()

{

    for(int i=;i<N;i++)

        for(int j=;j<=sqrt(i);j++)

            if(i%j == )

            {

                vi[i].push_back(j);

                if(j*j != i) vi[i].push_back(i/j);

            }

    int n;

    while(~scanf("%d",&n))

    {

        memset(l,,sizeof(l));

        memset(r,,sizeof(r));

        memset(vis,,sizeof(vis));

        ll ans = ;

        for(int i=;i<=n;i++)

            scanf("%d",&arr[i]);

        for(int i=;i<=n;i++)

        {

            int tp = ;

            for(int j=;j<vi[arr[i]].size();j++)

                tp = max(tp,vis[vi[arr[i]][j]]);

            l[i] = tp;

            vis[arr[i]] = i;

        }

        for(int i=;i<N;i++) vis[i] = n+;

        for(int i=n;i>;i--)

        {

            int tp = n+;

            for(int j=;j<vi[arr[i]].size();j++)

                tp = min(tp,vis[vi[arr[i]][j]]);

            r[i] = tp;

            vis[arr[i]] = i;

        }

        for(int i=;i<=n;i++)

            ans = (ans + 1LL*(i-l[i])*(r[i]-i) % mol) % mol;

        printf("%lld\n",ans);

    }

}

巴特西

HDU 5288 OO’s Sequence [数学]

HDU 5288 OO’s Sequence

最新文章

热门文章