HDU 5288 OO’s Sequence [数学]-白红宇

HDU 5288 OO’s Sequence [数学]

阅读量：4688 次

发布时间：2019-06-09

本文共 1284 字，大约阅读时间需要 4 分钟。

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

\sum i = 1 n \sum j = i n f (i, j) m o d （ 10 9 + 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

1 2 3 4 5

Sample Output

这题的题意是后来看了题解才懂的，意思是给定一个序列，对于每一个数，包括这个数的区间里的其他的数都不是这个数的因数，求对于每一个数的区间的个数的总和。

也就是说对于任何一个数，往左找到第一个它的因数的位置记作l，往右找到它的第一个因数的位置记作r，那么这个数对应的区间的个数是(i-l)*(r-i)，然后对所有的数求一个和就可以了。

因为这里数的范围只有1e4，所以一开始预处理1e4以内的数的因数存在vector[N]里。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))using namespace std;typedef long long ll;const int maxn = 1e5+3;const int N = 1e4+3;const int mol = 1e9+7;int arr[maxn],l[maxn],r[maxn],vis[N];vector 
                 
                   vi[N];int main(){ for(int i=1;i
                  
                   0;i--) { int tp = n+1; for(int j=0;j

转载于:https://www.cnblogs.com/HazelNut/p/7821067.html

你可能感兴趣的文章