【集训队互测2015】普罗达科特 - 题目

令 $N = \prod_{i = 1}^{n} p_{i}^{a_{i}}$ ， $M = \prod_{i = 1}^{n} p_{i}^{b_{i}}$ ，其中 $p_{i}$ 是两两不同的素数。

求将 $N$ 表示成 $k$ 个正整数的乘积的方案数，也就是 $N = \prod_{i = 1}^{k} x_{i}$ 的解的个数，答案对 $10^{9} + 21$ 取模。

对于子问题 $1$ ，要求对于所有整数 $i$ 满足 $1 \leq i < k$ ，都有 $x_{i} < x_{i + 1}$ 。

对于子问题 $2$ ，要求对于所有整数 $i$ 满足 $1 \leq i < k$ ，都有 $x_{i} \leq x_{i + 1}$ 。

对于两个子问题都要求对于所有整数 $i$ 满足 $1 \leq i \leq k$ 都有 $x_{i} ∤ M$ ，即 $x_{i}$ 不是 $M$ 的约数。

第一行两个正整数 $n, k$ 。

接下来一行 $n$ 个非负整数，第 $i$ 个整数表示 $a_{i}$ 。

接下来一行 $n$ 个非负整数，第 $i$ 个整数表示 $b_{i}$ 。

输入中没有给出 $p_{1}, \dots, p_{n}$ ，显然 $p_{i}$ 的取值并不影响答案。

一行两个整数，分别表示子问题 1 和 2 的答案。

5 3
5 5 4 5 5
3 0 3 2 3

295164 295326

10 5
13 11 17 7 9 2 11 11 10 12
7 9 4 15 18 4 9 7 4 2

75340090 59089865

共 10 个测试点，只有子问题 1 答案正确将获得 3 分，只有子问题 2 答案正确将获得 6 分，都正确将获得 10 分。

测试点编号	$n$	$a_{i}$	$b_{i}$	$k$
1	$\leq 5$	$\leq 5$	$\leq 5$	$\leq 3$
2	$\leq 10$	$\leq 20$	$\leq 20$	$\leq 5$
3	$= 1$	$\leq 10^{18}$	$\leq 10^{18}$	$\leq 25$
4	$\leq 50$	$\leq 10^{3}$	$= 0$	$\leq 20$
5		$\leq 10^{18}$	$= 0$	$\leq 25$
6		$\leq 10^{3}$	$\leq 10^{3}$	$\leq 10$
7		$\leq 10^{18}$	$\leq 10^{18}$	$\leq 10$
8				$\leq 15$
9				$\leq 20$
10				$\leq 25$

时间限制： $3 s$

空间限制： $256 MB$

中国国家集训队互测2015 - By 杜瑜皓

Universal Online Judge