hdu 5288 OO’s Sequence（2015多校第一場第1題）枚舉因子，hdu5288
題目鏈接：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
