[R79D]分装 - 代码源竞赛平台

时空限制

1S/512M

题目描述

仓库里有 $n$ 堆物品，第 $i$ 堆有 $a_i$ 件。管理员准备用同一种容量的箱子分别分装每堆物品：每箱装 $d$ 件，装不满一箱的余数留在原处。因此，第 $i$ 堆可以装满的箱数为

$$c_i=\left\lfloor\frac{a_i}{d}\right\rfloor.$$

管理员另有一份长度为 $n$ 的箱数记录 $b$，但记录的顺序已经打乱。若每个非负整数在 $c$ 和 $b$ 中出现的次数都相同，就称容量 $d$ 合法。不同堆可以有相同的箱数，箱数为 $0$ 的堆也需要计入。

给定数组 $a,b$ 和正整数 $M$，求 $1\le d\le M$ 的整数中有多少个合法容量。每个容量计数一次，数组之间存在多种对应方式时也计数一次。

格式

输入格式

第一行包含两个正整数 $n,M$，分别为物品堆数和允许的箱子容量上限。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 为第 $i$ 堆物品的件数。

第三行包含 $n$ 个非负整数 $b_1,b_2,\ldots,b_n$，为顺序已经打乱的箱数记录。

输出格式

输出一个非负整数，表示合法容量 $d$ 的数量。答案不取模。

样例

样例输入 #1

3 10
30 10 20
2 3 1

样例输出 #1

3

样例输入 #2

3 10
5 1 5
1 1 0

样例输出 #2

3

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$1000$	A
$2$	$20$	$2\times10^5$	B
$3$	$50$		无

特殊性质 A：$M\le1000$。

特殊性质 B：对于所有 $1\le i\le n$，都有 $b_i=0$。

对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$1\le M\le10^{18}$，$0\le a_i,b_i\le10^{18}$。