题目：?pid=5288
题意：区间[L,R],若L<=i<=R,对于所有的i，满足a[i]%a[j]!=0（i!=j）则i对答案的贡献+1。求出所有区间的答案和，其中1<=L<=R<=N。
分析：求出每个数对答案的贡献即可。对于每个a[i],求左边离a[i]最近且可以整出a[i]的位置L[i]和右边离a[i]最近且可以整出a[i]的位置R[i],那么a[i]对答案的贡献就是(R[i]-i)*(i-L[i])。怎么求L[i],首先将每个数的位置按输入顺序存在数组里面，枚举a[i]的因子,每枚举a[i]的一个因子,二分找到离a[i]左边和右边最近的位置,更新位置。
代码：
#include <iostream>#include <cstdio>#include <vector>#include <algorithm>using namespace std;const int maxn = 1e5+6;const int mod = 1e9+7;vector <int > fac[10006];vector <int > pos[10006];int a[maxn],L[maxn],R[maxn];void Init(){int i,j;for(i=1;i<10005;i++){for(j=1;j*j<=i;j++){if(i%j==0){fac[i].push_back(j);if(i/j!=j)fac[i].push_back(i/j);}}}}int Find_L(int f,int p){int down=0,mid,up=pos[f].size()-1,ret=-1;while(down<=up){mid=(up+down)>>1;if(pos[f][mid]>=p)up=mid-1;else{down=mid+1;if(ret<pos[f][mid])ret=pos[f][mid];}}return ret;}int Find_R(int f,int p){int down=0,mid,up=pos[f].size()-1,ret=1e9;while(down<=up){mid=(up+down)>>1;if(pos[f][mid]<=p)down=mid+1;else{up=mid-1;if(ret>pos[f][mid])ret=pos[f][mid];}}return ret;}int main(){Init();int n,i,j;while(scanf("%d",&n)!=EOF){for(i=0;i<=10000;i++)pos[i].clear();for(i=0;i<n;i++){scanf("%d",&a[i]);pos[a[i]].push_back(i);L[i]=-1;R[i]=n;}for(i=0;i<n;i++){for(j=0;j<fac[a[i]].size();j++){int f=fac[a[i]][j];int l=Find_L(f,i);int r=Find_R(f,i);L[i]=max(l,L[i]);R[i]=min(r,R[i]);}}long long ans=0;for(i=0;i<n;i++)ans=(ans+(R[i]-i)*(i-L[i])%mod)%mod;printf("%I64d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，烦恼忧愁不用追，吃点好的别嫌贵，
