题目数据范围$n\le 10^5$，$O(n^2)$的暴力必定超时。但是，$0<a[i] \le 10000$，可以先求出1~10000每个数的因子（vector）。

接下来，运用一个思想：

前不见古人，后不见来者。

即：对于每个位置i，找到左边最近的“古人”j，记为l[i]，满足a[j]是a[i]的因子；找到右边最近的“来者”k，记为r[i]，满足a[k]是a[i]的因子，就有$(i-j)\cdot (k-i)$个区间的f值可以加一。

为了$O(n\sqrt{\max(a[i])})$的实现，需要一个pos数组，记录每个数字最近的出现位置。对于每个位置i，遍历a[i]的因子，寻找最接近i的因子出现的位置（左侧找最大，右侧找最小）。pos用之前要初始化（左侧设为0，算时先将l[i]设为0；右侧设为$\le n+1$的值，算时先将r[i]设为n+1），保证因子在左侧/右侧。

注意：vector有两种等价的遍历方法，不可以混（以下摘自李煜东《算法竞赛进阶指南》）。

定义：

vector
     
       a;
     

 

第一种：

for(int i=0;i

 

第二种：

for(vector
      
       ::itetator it=a.begin();it!=a.end();it++)    cout<<*it<