题目链接：?pid=5288
题面：
OO’s SequenceTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 985Accepted Submission(s): 375
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
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 arraySecond line:contain n numbers ai(0<ai<=10000)
Output
For each tests: ouput a line contain a number ans.
Sample Input
51 2 3 4 5
Sample Output
23
Author
FZUACM
Source
解题：
只想到从左到右去找最近的不合法点，没想到从右往左找，那么答案就出来了。其实数据范围那么小，就已经是一种暗示了。可以用数组记录下其最后出现的位置。注意扫的操作，要和记录同时进行。注意小心处理1的情况就好。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <map>#include <vector>#include <cmath>#include <algorithm>#define mod 1000000007#define maxn 100010#define LL long long using namespace std;int t,le[100010],ri[100010],store[100010],pre[100010],tmp,root;LL ans;int main(){while(~scanf("%d",&t)){ans=0;for(int i=1;i<=t;i++)scanf("%d",&store[i]);for(int i=1;i<=t;i++)pre[i]=0;for(int i=1;i<=t;i++){tmp=1;root=sqrt((double)store[i]);for(int j=1;j<=root;j++){if(store[i]%j==0){tmp=max(tmp,pre[j]+1);tmp=max(tmp,pre[store[i]/j]+1);}}le[i]=tmp;pre[store[i]]=i;}for(int i=1;i<=t;i++)pre[i]=t+1;for(int i=t;i>=1;i–){tmp=t;root=sqrt((double)store[i]);for(int j=1;j<=root;j++){if(store[i]%j==0){tmp=min(pre[j]-1,tmp);tmp=min(tmp,pre[store[i]/j]-1);}}ri[i]=tmp;pre[store[i]]=i;}/*for(int i=1;i<=t;i++)cout<<i<<" "<<le[i]<<" "<<ri[i]<<endl;*/for(int i=1;i<=t;i++){ans=(ans+1LL*(i-le[i]+1)*(ri[i]-i+1))%mod;}printf("%lld\n",ans);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
你在无垠的海边第一次听到了自己心跳的声音，
