自动搬运

查看原文

来自洛谷，原作者为

	EricWan 一只菜鸡。

搬运于2025-08-24 22:31:34，当前版本为作者最后更新于2023-05-18 19:00:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题数据范围还是很小的，于是考虑暴力。

这里枚举 $n \times m$ 个数对，如果有公因数，就约掉，并累成在答案里。

可以发现，不可能有一个约数约不掉。

看看数据范围，$O(n \times m \times \log_2 \max\{\max_{i = 1}^{n}A_i,\max_{i = 1}^{m}B_i\})$ 能过，于是，就可以开心的写代码了。

AC 代码部分 main 函数：

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		k = gcd(a[i],b[j]);
 		a[i] /= k;
		b[j] /= k;
		ans *= k;
		if (ans >= mod) flag = 1;
		ans %= mod;
	}
}