「HOI R1」杂分选约

ID: 9586

远端评测题

200ms

512MiB

尝试: 0

已通过: 0

难度: 6

上传者:

root

标签>

2024

O2优化

洛谷比赛

题目背景

请注意本题并不寻常的时间限制。

由于 python 自带对于高精度乘法的实现，并且运行效率较高，导致其编写的暴力程序，在一般的时间限制下可以通过绝大部分点。故本题时限开到 $200\text{ms}$ 。

黄总是一名计算很强的数学老师，以黄氏约分而闻名。现在他请小 $\iiint$ A 了这道题。但小 $\iiint$ 似乎有点菜，所以求助于你。

题目描述

把

\dfrac{\displaystyle\prod_{i=1}^n a_i}{\displaystyle\prod_{j=1}^m b_j}

表示为最简分数 $^{[1]}$ $\dfrac{p}{q}$ ，求 $p$ 和 $q$ 。

好心的同学还给了小 $\iiint$ 一个整数 $C$ ，即数据点所在的 Subtask。

输入格式

第一行三个整数 $n,m$ 和 $C$ 。

第二行 $n$ 个整数 $a_{1\dots n}$ 。

第三行 $m$ 个整数 $b_{1\dots m}$ 。

输出格式

第一行两个数 $p$ 和 $q$ 。

输入数据 1

6 8 0
540000 350000 110000 130000 170000 970000
2000 5000 1000 1000 97000 17000 143000 210000

输出数据 1

9 10

提示

注释

$[1]$ ：百度百科：最简分数，是分子、分母只有公因数 $1$ 的分数，或者说分子和分母互质的分数，又称既约分数。如：二分之一，三分之二，九分之八，八分之三等等。

样例解释

$\dfrac{540000\times350000\times110000\times130000\times170000\times970000}{2000\times5000\times1000\times1000\times97000\times17000\times143000\times210000}=\dfrac{9}{10}$ ， $\gcd(9,10)=1$

数据规模与约定

本题采用捆绑测试。

Subtask	分值	数据范围
#0	0	同样例
#1	$5$	$1\le n,m\le500$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p,q\le3\times10^9$
#2	$5$	$1\le n,m\le25000$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p,q\le10$
#3	$10$	$1\le n,m\le5000$ ， $1\le a_i,b_i\le3\times10^9$ ， $1\le p,q\le3\times10^9$
#4	$15$	$1\le n,m\le10000$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p,q\le3\times10^9$
#5	$20$	$1\le n,m\le25000$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p\le3\times10^9$ ， $q=1$
#6	$10$	$1\le n,m\le25000$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p\le3\times10^9$ , $1\le q \le25000$
#7	$20$	$1\le n,m\le25000$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p,q\le3\times10^9$
#8	$10$	$1\le n,m\le10^6$ ， $1\le a_i,b_i\le10^6$ ， $1\le p,q\le3\times10^9$
#9	$5$	$1\le n,m\le10^6$ ， $1\le a_i,b_i\le9\times10^{18}$ ， $1\le p,q\le3\times10^9$

提示

~~高精度狗都不写。~~

本题时限较小且输入量较大，若你认为自己的算法复杂度正确，请尝试优化读写速度。

#P10383. 「HOI R1」杂分选约