题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5288
转换成求从1到n可以整除A[i]的区间的数量。
找离最近的A[i]最近的可以整除A[i]的l和r，因为再往左或者右必然包含l和r
假如[l,i]有x个数字，[i,r]有y个数字，那么A[i]的贡献即(x+1)*(y+1)
求A[i]对ans的贡献综合
即求离A[i]最近的可以被A[i]整除的数
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 #include <iostream> 6 #include <cmath> 7 #include <queue> 8 #include <map> 9 #include <stack> 10 #include <list> 11 #include <vector> 12 13 using namespace std; 14 15 inline int max(int a, int b) { 16 return a > b ? a : b; 17 } 18 19 const int maxn = 100010; 20 const int mod = 1000000007; 21 int a[maxn]; 22 int s[maxn]; 23 int l[maxn]; 24 int r[maxn]; 25 int n; 26 long long ans; 27 28 void left() { 29 int m = 0; 30 memset(s, 0, sizeof(s)); 31 for(int i = n; i >= 1 ; i--) { 32 m = max(m, a[i]); 33 for(int j = a[i]; j <= m; j+=a[i]) { 34 if(s[j] && l[s[j]] < i) { 35 l[s[j]] = i; 36 } 37 s[a[i]] = i; 38 } 39 } 40 } 41 42 void right() { 43 int m = 0; 44 memset(s, 0, sizeof(s)); 45 for(int i = 1; i <= n; i++) { 46 m = max(m, a[i]); 47 for(int j = a[i]; j <= m; j+=a[i]) { 48 if(s[j] && r[s[j]] > i) { 49 r[s[j]] = i; 50 } 51 s[a[i]] = i; 52 } 53 } 54 } 55 int main() { 56 freopen("in", "r", stdin); 57 while(~scanf("%d", &n)) { 58 ans = 0; 59 for(int i = 1; i <= n; i++) { 60 scanf("%d", &a[i]); 61 l[i] = 0; 62 r[i] = n + 1; 63 } 64 right(); 65 left(); 66 // for(int i = 1; i <= n; i++) { 67 // printf("%d %d %d ", l[i], a[i], r[i]); 68 // } 69 for(int i = 1; i <= n; i++) { 70 ans = (ans + ((i - l[i]) % mod * (r[i] - i)) % mod) % mod; 71 } 72 printf("%I64d ", ans); 73 } 74 }