hdu5288(OO’s Sequence)

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 _imod a _j=0,now OO want to know

（ ）

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

题意：给定一个正整数序列a，f(l,r)表示在a[l...r]中的a[i]，对于a[l...r]中的每一个数a[j]都有a[i]%a[j]!=0的i数目(i!=j)。最后求：

（）

题解：稍加思考很简单的一道题，设l[i]、r[i]分别表示a[i]左右最近的约数的下标，不存在则分别为-1和n。注意到a[i]<10000，所以可以用一个标记数组flag来标记a[i]某个约数是否出现过。最终答案为sigma[(i-l[i])*(r[i]-i)]mod(1e10+7)

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;

int a[100010], l[100010], r[100010], flag[10010];

int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        fill(l, l+n, -1);
        fill(r, r+n, n);
        //计算a[i]左端最近的约数
        memset(flag, -1, sizeof(flag));
        for (int i = 0; i < n; ++i)
        {
            for (int j = 1; j*j <= a[i]; ++j)
                if (a[i] % j == 0)
                {
                    if (flag[j] != -1)
                        l[i] = max(l[i], flag[j]);
                    if (flag[a[i]/j] != -1)
                        l[i] = max(l[i], flag[a[i]/j]);
                }
            flag[a[i]] = i;
        }
        //计算a[i]右端最近的约数
        memset(flag, -1, sizeof(flag));
        for (int i = n-1; i >= 0; --i)
        {
            for (int j = 1; j*j <= a[i]; ++j)
                if (a[i] % j == 0)
                {
                    if (flag[j] != -1)
                        r[i] = min(r[i], flag[j]);
                    if (flag[a[i]/j] != -1)
                        r[i] = min(r[i], flag[a[i]/j]);
                }
            flag[a[i]] = i;
        }

        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = (ans + (i - l[i]) * (r[i] - i)) % 1000000007;
        printf("%d\n", ans);
    }
    return 0;
}

算法码上来文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。