题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5288
题意：在闭区间[l,r]内有一个数a[i]，a[i]不能整除 除去自身以外的其他的数，f(l,r)表示在这区间内a[i]这样的数的个数，，现给你n个数，求所有区间的f(l,r)的和。
思路：对于每个数a[i]求出他的左右侧最靠近他的且是他的因子的位置L、R，并记录，那么对于每个数a[i]都有了他的L，R，而对于每个a[i]在f(l,r)有价值的次数之和就是(i-L+1)*(R-i+1)
代码：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <algorithm> 8 #include <vector> 9 using namespace std; 10 #define LL __int64 11 #define INF 0x3f3f3f3f 12 const int MAXN=100005; 13 #define mod 1000000007 14 int l[MAXN]; 15 int r[MAXN]; 16 int a[MAXN]; 17 int visl[MAXN]; 18 int visr[MAXN]; 19 LL ans; 20 int main() 21 { 22 int n,i,j; 23 while(~scanf("%d",&n)) 24 { 25 memset(visl,0,sizeof(visl)); 26 memset(visr,0,sizeof(visr)); 27 for(i=1;i<=n;i++) 28 { 29 scanf("%d",&a[i]); 30 l[i]=1; 31 r[i]=n; 32 } 33 for(i=1;i<=n;i++) 34 { 35 for(j=a[i];j<=10000;j+=a[i]) 36 { 37 if(visr[j]&&r[visr[j]]==n) 38 r[visr[j]]=i-1; 39 } 40 visr[a[i]]=i; 41 } 42 for(i=n;i>0;i--) 43 { 44 for(j=a[i];j<=10000;j+=a[i]) 45 { 46 if(visl[j]&&l[visl[j]]==1) 47 l[visl[j]]=i+1; 48 } 49 visl[a[i]]=i; 50 } 51 ans=0; 52 for(i=1;i<=n;i++) 53 { 54 //printf("%d %d\n",l[i],r[i]); 55 ans+=(LL)(i+1-l[i])*(r[i]-i+1); 56 ans%=mod; 57 } 58 printf("%I64d\n",ans%mod); 59 } 60 return 0; 61 } View Code
转载于:https://www.cnblogs.com/yjx-xx/p/4667725.html
