2017-2018年问题求解(三)期末上机考试 Day1 题解

A. 智能机器

题意:求 $latex \sum_{i=l}^r d(i^k)$ 模 16290047,其中 $latex d(n)$ 表示 $latex n$ 的约数个数。

数据范围:$latex r – l \leq 10^6, l \leq r \leq 10^{12}, k \leq 10^6$。

题解:首先,对于任意正整数 $latex n$,如果它的唯一分解为

$$ n = q_1^{a_1} q_2^{a_2} \cdots q_m^{a_m} $$

那么它的约数个数就是

$$ d(n) = (1+a_1)(1+a_2)\cdots(1+a_m) $$

从而

$$ d(n^k) = (1+ka_1)(1+ka_2)\cdots(1+ka_m) $$

这样,我们只要对每个要求的 $latex i$,找出所有形如 $latex p^x | i$ 中 $latex x$ 最大的因子。注意到这样的因子不可能超过 $latex \sqrt{i}$,除非 $latex x = 1$。从而我们对素数 $latex p$,可以枚举 l~r 区间范围内的 $latex rp^x$ 形式的数(其中 $latex r$ 不是 $latex p$ 的倍数),并乘上 $latex kx+1$ 的贡献。如果某个数除以所有枚举过的 $latex p^x$ 形式的因子仍然不为 1,说明剩下的数一定是一个素数,那么还要乘上 $latex k+1$ 的贡献。

经过仔细的分析,上述三重循环枚举的时间复杂度实际上不会超过 $latex O(\frac{\sqrt{r}}{\log r} \log (r – l))$,完全可以接受。

B.  Lunatic

题意:一共有 $latex n$ 个动作,每个动作可以在 $latex [l_i, r_i]$ 之间的某个时刻完成,完成后可得到 $latex v_i$ 分数。每一时刻只能做一样动作,计算最多能拿多少分。

数据范围:$latex 1 \leq n \leq 1000, 1 \leq s_i \leq t_i \leq 30000, 1 \leq v_i \leq 1000$

题解:显然是带权二分图的最大权匹配。考场上没带 Kuhn-Munkres 的板子,只好敲费用流,最后 2 分钟卡过去的…(不过这题用裸的 KM 算法应该也过不了 233)其实这题标答是贪心匹配,将边按收益排序,优先匹配收益高的就行了…

说一下费用流的做法吧。每个动作连一条容量为 1,费用为 $latex -v_i$ 的边到 $latex [l_i, r_i]$ 中的每个时间点,源点到每个动作连费用为 0 容量为 1 的边,每个时间点连费用为 0 容量为 1 的边到汇点,然后跑最小费用流取负就好了。不过这样是过不了全部数据的,要过全部数据,还要加两个优化:一是把时间区间离散化;二是如果某个动作有 $latex r_i – l_i + 1 \geq n$,那么这个动作一定可以在某个时刻完成,就不需要加到图里面了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注