2015 Multi-University Training Contest 1 Solutions – xuan's blog

2015 Multi-University Training Contest 1 Solutions – xuan's blog

题意：给出一个数组 $a[n]$ ，定义函数 $f(l,r)$ 表示在区间 $[l,r]$ 内没有 $a_i$ 的因子的 $i$ 的数量，因子的下标不能为 $i$ ，求

$$\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)\mod(10^9+1)$$

 

题目可以转换成每个 $a_i$ 可以贡献的区间个数为 $K_i$ ，求出所有 $K_i$ 之和

要求 $K_i$ 就是找左右离 $a_i$ 最近的 2 个因子，求出左右不包含因子的区间长度 $l,r$

$$K_i=(l+1)\times (r+1)$$

$$ans=\sum_{i=1}^{n}K_i$$

要求出最近的因子可以预处理 10000 内所有数的因数，在输入的时候记录每个数出现的位置，因为记录是有序的，所以可以找出离 $a_i$ 最近的两个因子

Read full article from 2015 Multi-University Training Contest 1 Solutions – xuan's blog