UOJ Logo Universal Online Judge

UOJ

#99. 【集训队互测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 \nmid M$,即 $x_i$ 不是 $M$ 的约数。

输入格式

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

接下来一行 $n$ 个非负整数,第 $i$ 个整数表示 $a_i$。

接下来一行 $n$ 个非负整数,第 $i$ 个整数表示 $b_i$。

输入中没有给出 $p_1, \dots, p_n$,显然 $p_i$ 的取值并不影响答案。

输出格式

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

样例一

input

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

output

295164 295326

样例二

input

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

output

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}$$\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\texttt{s}$

空间限制:$256\texttt{MB}$

来源

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

下载

样例数据下载