hdu 5288 数学 ****-白红宇

hdu 5288 数学 ****

阅读量：5124 次

发布时间：2019-06-13

本文共 1521 字，大约阅读时间需要 5 分钟。

给一个序列

定义函数f(l ,r) 为区间[l ,r] 中

的数ai不是在这个区间其他任意数aj的倍数

求所有f(l,r)之和

通过预处理，记录 a[i] 的左右边界（所谓的左右边界时在从 a[i] 当前位置往左往右找，找到左边第一个和右边第一个能够整除 a[i] 的数，这两个数就是a[i]的左右边界）然后记录到 l[] & r[] 中，这样 a[i] 对 ans 的贡献是 (i - l[i]) * (r[i] - i);在预处理 l[] 数组时，用pre[j]标记一下 j （表示 j 最后一次出现的位置），如果 j 在之前已经遇到过且右边界没有被更新过，就将 pre[j] 的边界更新到当前 i 所在的位置。

前面做标记，后面遇到时再将记录的值更新到对应的l，r里

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 using namespace std; 9 #define MOD 100000000710 const int INF=0x3f3f3f3f;11 const double eps=1e-5;12 typedef long long ll;13 #define cl(a) memset(a,0,sizeof(a))14 #define ts printf("*****\n");15 const int MAXN=100010;16 int n,m,tt;17 int a[MAXN];18 ll l[MAXN],r[MAXN],pre[MAXN];19 int main()20 {21 int i,j,k,ca=1;22 #ifndef ONLINE_JUDGE23 freopen("1.in","r",stdin);24 #endif25 while(~scanf("%d",&n))26 {27 for(i=1;i<=n;i++)28 {29 scanf("%d",a+i);30 l[i]=0,r[i]=n+1;31 }32 cl(pre);33 for(i=1;i<=n;i++)34 {35 for(j=a[i];j<=10000;j+=a[i])36 {37 if(pre[j]&&r[pre[j]]==n+1) //保证是第一个遇到的,因此更新过的就不能再更新了38 {39 r[pre[j]]=i;40 }41 }42 pre[a[i]]=i;43 }44 cl(pre);45 for(i=n;i>0;i--)46 {47 for(j=a[i];j<=10000;j+=a[i])48 {49 if(pre[j]&&l[pre[j]]==0)50 {51 l[pre[j]]=i;52 }53 }54 pre[a[i]]=i;55 }56 ll ans=0;57 for(i=1;i<=n;i++)58 {59 ans+=(ll)(((i-l[i])*(r[i]-i))%MOD);60 ans=(ans%MOD+MOD)%MOD;61 }62 printf("%I64d\n",ans);63 }64 }

转载于:https://www.cnblogs.com/cnblogs321114287/p/4801034.html

你可能感兴趣的文章