OO’s Sequence
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5288
Mean:
给定一个数列，让你求所有区间上满足Ai%Aj!=0（Ai!=Aj）的Ai的个数之和。
analyse:
对于Ai，如果我们知道最靠近Ai且能够整除Ai的数的下标l和r，那么Ai对答案的贡献就是(r-i)*(i-l)。剩下的就是怎样去求每个Ai的l和r了。
首先我们预处理出：对于每个i，能够被1~i整除的数，用链表存起来。
那么对于输入的数列Ai，我们就可以在O(1)的时间复杂度内知道他能够被哪些数整除，然后去找这些数在pos数组中映射的位置。
从左往右求出每个Ai的l，从右往左求出每个Ai的r，然后O(n)扫一遍统计答案。
Time complexity: O(N*sqrt(A))
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-22-08.50
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 10005, MAXX = 100005, mod = 1e9 + 7;
vector<int> divi[MAXN];
int a[MAXX], l[MAXX], r[MAXX], pos[MAXX], n;
void init()
{
for( int i = 1; i <= 10000; ++i )
for( int j = 1; j <= i; ++j )
if( !( i % j ) ) divi[i].push_back( j );
}
int main()
{
ios_base::sync_with_stdio( false );
cin.tie( 0 );
init();
while( cin >> n )
{
for( int i = 0; i < n; ++i ) cin >> a[i];
memset( l, -1, sizeof l );
memset( r, 0x3f, sizeof r );
memset( pos, -1, sizeof pos );
for( int i = 0; i < n; ++i )
{
int lef = -1;
for( int j = 0; j < divi[a[i]].size(); ++j )
lef = max( lef, pos[divi[a[i]][j]] );
pos[a[i]] = i;
l[i] = lef;
}
memset( pos, 0x3f, sizeof pos );
for( int i = n - 1; i >= 0; --i )
{
int rig = 0x3f3f3f3f;
for( int j = 0; j < divi[a[i]].size(); ++j )
rig = min( rig, pos[divi[a[i]][j]] );
pos[a[i]] = i;
r[i] = rig;
}
int ans = 0, L, R;
for( int i = 0; i < n; ++i )
{
if( l[i] == -1 ) L = i + 1;
else L = i - l[i];
if( r[i] == 0x3f3f3f3f ) R = n - i;
else R = r[i] - i;
ans = ( L * R % mod + ans ) % mod;
}
cout << ans << endl;
}
return 0;
}
/*
*/
