预处理出每一个数字的左右两边能够整除它的近期的数的位置
OO’s Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1880 Accepted Submission(s): 672
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(0<ai<=10000)
In each test case:
First line: an integer n(n<=10^5) indicating the size of array
Second line:contain n numbers ai(0<ai<=10000)
Output
For each tests: ouput a line contain a number ans.
Sample Input
5
1 2 3 4 5
Sample Output
23
Author
FZUACM
Source
/* ***********************************************
Author :CKboss
Created Time :2015年07月24日 星期五 08时12分15秒
File Name :HDOJ5288.cpp
************************************************ */ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map> using namespace std; typedef long long int LL; const int maxn=100100;
const LL MOD=(LL)(1e9+7); int n;
int a[maxn];
int Left[maxn],Right[maxn];
vector<int> pos[10010]; void init()
{
for(int i=0;i<=10010;i++)
{
pos[i].clear();
}
for(int i=0;i<n;i++)
{
Left[i]=0; Right[i]=n-1;
}
} void pre()
{
for(int i=0;i<n;i++)
{
int x=a[i];
for(int j=x;j<=10000;j+=x)
{
for(int k=0,sz=pos[j].size();k<sz;k++)
{
int z=pos[j][k];
if(z==i) continue;
else if(z<i)
{
Right[z]=min(Right[z],i-1);
}
else if(z>i)
{
Left[z]=max(Left[z],i+1);
}
}
}
}
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout); while(scanf("%d",&n)!=EOF)
{
init();
for(int i=0;i<n;i++)
{
scanf("%d",a+i);
pos[a[i]].push_back(i);
}
pre();
LL ans=0;
for(int i=0;i<n;i++)
{
LL L=i-Left[i]+1LL;
LL R=Right[i]-i+1LL;
ans=(ans+(L*R)%MOD)%MOD;
}
cout<<ans<<endl;
} return 0;
}