程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu5288(2015多校1)OO’s Sequence

hdu5288(2015多校1)OO’s Sequence

編輯:關於C++

 

 

OO’s Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 353 Accepted Submission(s): 117



Problem 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 ai mod aj=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 ai(0i<=10000)

Output For each tests: ouput a line contain a number ans.
Sample Input
5
1 2 3 4 5

Sample Output
23

f(l,r)求[l,r]區間內存在多少i(區間內沒有i的約數)。公式中給出的區間,也就是所有存在的區間。

 

記錄l[i],r[i],i的約數存在的位置,要求最接近i的。可以用數組記錄下出現的最接近當前位置的數。得到l[i],r[i]後,那麼i可以被計數的區間也就有了,左邊界為l[i]到i,右邊界為i到r[i],那麼i一共會被記錄(i-l[i])*(r[i]-i)次,累加所有的計數。

 

#include 
#include 
#include 
using namespace std ;
#define LL __int64
const int MOD = 1e9+7 ;
int a[100010] , l[100010] , r[100010] ;
int Map[10010] ;
int main() {
    int i , j , n ;
    LL ans ;
    while( scanf(%d, &n) != EOF ) {
        for(i = 1 ; i <= n ; i++)
            scanf(%d, &a[i]) ;
        memset(Map,0,sizeof(Map)) ;
        for(i = 1 ; i <= n ; i++) {
            for(j = 1 , l[i] = 0 ; j*j <= a[i] ; j++) {
                if( a[i]%j ) continue ;
                if( Map[j] ) l[i] = max(l[i],Map[j]) ;
                if( Map[a[i]/j] ) l[i] = max(l[i],Map[a[i]/j]) ;
            }
            Map[a[i]] = i ;
        }
        memset(Map,0,sizeof(Map)) ;
        for(i = n ; i > 0 ; i--) {
            for(j = 1 , r[i] = n+1 ; j*j <= a[i] ; j++) {
                if( a[i]%j ) continue ;
                if( Map[j] ) r[i] = min(r[i],Map[j]) ;
                if( Map[a[i]/j] ) r[i] = min(r[i],Map[a[i]/j]) ;
            }
            Map[a[i]] = i ;
        }
        for(i = 1 , ans = 0 ; i <= n ; i++) {
            ans = (ans + (i-l[i])*(r[i]-i) ) % MOD ;
        }
        printf(%I64d
, ans) ;
    }
    return 0 ;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved