中国传媒大学程序设计竞赛 AB 题解
出题人来个A, B 的题解:
A:
考虑区间和本质上就是一段前缀和减去另一段前缀和,因此我们尽量让这个差值尽可能大即可,那就可以直接维护“前缀和数组 ” 的前缀最小值 和后缀最大值 ,每个 的答案就是 。
B:
考虑 ,同时
因此 ,两者要想前者大于等于后者,当且仅当取等号,即:。
而
,说明 是 的因子。
,说明 是 的倍数。
因此只需要预处理出 以内所有数字的倍数个数和因子个数(这步可以调和级数 )。
接着枚举 ,答案加上 的因子数乘 的倍数即可。