CF645F Cowslip Collections

为了与 Mischievious Mess Makers 缔结和平，Bessie 和 Farmer John 计划种植一些花园，以点缀 Bovinia 郁郁葱葱的草地。作为一名优秀的园艺师，他们知道每个花园的花卉排列必须完全相同。最初，Farmer John 有 $n$ 种不同的花可供选择，第 $i$ 种花有 $a_{i}$ 朵。 在接下来的 $q$ 天里，Farmer John 每天都会收到一种新花卉的若干朵。在第 $j$ 天，他会收到 $c_{j}$ 朵同种新鲜花卉，这种花是与 Farmer John 现有的所有花种不同的新花种。 Farmer John 在奢侈与极简之间保持恰到好处的平衡，他希望选用恰好 $k$ 种花卉，并且，为了减少浪费，被选中 $k$ 种花的所有花朵都必须用来种植到某个花园中。同时，每个花园都必须完全相同；也就是说，对于任意被选的 $k$ 种花，每种花在每个花园里的数量都应相同。Farmer John 推崇国家平等，希望能够建设尽可能多的花园。 在每一天收到新花之后，Farmer John 想知道在所有可能的 $k$ 种花组合下，他最多可以建成的花园数目的总和。由于答案可能很大，请输出对 $10^{9}+7$ 取模的结果。

输入的第一行包含三个整数 $n$、$k$ 和 $q$，满足 $1 \leq k \leq n \leq 100000$，$1 \leq q \leq 100000$。 接下来 $n$ 行，每行为一个整数 $a_{i}$（$1 \leq a_{i} \leq 1000000$），表示 Farmer John 最初拥有的第 $i$ 种花的数量。 之后 $q$ 行，每行为一个整数 $c_{j}$（$1 \leq c_{j} \leq 1000000$），表示第 $j$ 天收到的新花（新种类）数量。

每次收到新花后，输出所有可能的 $k$ 种花组合下的最大花园数量的和，结果对 $10^9+7$ 取模。

在第一个样例中，第一天后 Farmer John 拥有 $(4,6,9,8)$ 种花，$k=3$。 选取 $(4,6,8)$ 时，他可以建 $2$ 个花园，每个花园分别有 $(2,3,4)$ 朵花。选 $(4,6,9)$、$(4,9,8)$、$(6,9,8)$ 时只能建 $1$ 个花园，因为这些组合没有能整除每种数量的花园数。所以所有 $k=3$ 种组合下花园数之和为 $2+1+1+1=5$。 第二天，Farmer John 拥有 $(4,6,9,8,6)$ 种花。所有组合下的和为 $1+2+2+1+1+2+2+3+1+1=16$。 在第二个样例中，$k=1$。拥有 $x$ 朵某种花就可以建 $x$ 个花园。因此答案分别为 $6+5+4+3+2=20$ 和 $6+5+4+3+2+1=21$。 由 ChatGPT 5 翻译