题目链接：HDU 5288 OO’s Sequence
题意：给出一个n，表示n个数的序列，函数f（l,r）定义，在l,r区间中存在多少个数，不能被其他数整除。求累加所有子区间的函数值
思路：从ai的小范围入手
1.a不能被b整除，即a的所有因子中不存在b，所以打表枚举所有的数的因子。
2.找到一个数(位置为i)满足条件时最左端l和最右端r，（i-l）*（r-i）就是对答案的贡献。
AC代码：
#include <stdio.h>#include <algorithm>#include <vector>#include <string.h>#define LL __int64using namespace std;int a[100010];vector<int> mp[10010];int l[100010],r[100010];//l:在第i个数的左边离a[i]最近的能整除a[i]的数的位置int vis[10010];const LL kmod=1e9+7;void init(){int i,j;for(i=1;i<=10000;i++){mp[i].clear();for(j=1;j<=i;j++){if(i%j==0)mp[i].push_back(j);}}}int main(){int i,j,n;init();while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++){scanf("%d",&a[i]);}for(i=1;i<=n;i++) l[i]=1;memset(vis,0,sizeof vis);for(i=1;i<=n;i++){int sz=mp[a[i]].size();for(j=0;j<sz;j++){int tmp=mp[a[i]][j];if(vis[tmp]==0 || a[i]%tmp!=0)//因子未出现或者不是a[i]的因子continue;l[i]=max(l[i],vis[tmp]+1);//取一个最右边的点}vis[a[i]]=i;//记录a[i]的下标，，}for(i=1;i<=n;i++) r[i]=n;memset(vis,0,sizeof vis);for(i=n;i>=1;i–){int sz=mp[a[i]].size();for(j=0;j<sz;j++){int tmp=mp[a[i]][j];if(vis[tmp]==0 || a[i]%tmp!=0) //先判断tmp（其实就是a[i]中是否有等于tmp）是否存在，then判断是否能被整除continue;r[i]=min(r[i],vis[tmp]-1);}vis[a[i]]=i;}LL ans=0;for(i=1;i<=n;i++){LL tmp=(LL)(i-l[i]+1)*(r[i]-i+1);printf("%d %d = %d\n",l[i],r[i],tmp);ans=(ans+tmp)%kmod;}printf("%I64d\n",ans);}return 0;}/*51 2 6 4 5*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
一个今天胜过两个明天
