{"problem":{"name":"「HOI R1」杂分选约","description":{"content":"把 $$\\dfrac{\\displaystyle\\prod_{i=1}^n a_i}{\\displaystyle\\prod_{j=1}^m b_j}$$ 表示为*最简分数 $^{[1]}$* $\\dfrac{p}{q}$，求 $p$ 和 $q$。 好心的同学还给了小 $\\iiint$ 一个整数 $C$，即数据点所在的 Subtask。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":200,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10383"},"statements":[{"statement_type":"Markdown","content":"把\n$$\\dfrac{\\displaystyle\\prod_{i=1}^n\na_i}{\\displaystyle\\prod_{j=1}^m b_j}$$\n表示为*最简分数 $^{[1]}$* $\\dfrac{p}{q}$，求 $p$ 和 $q$。\n\n好心的同学还给了小 $\\iiint$ 一个整数 $C$，即数据点所在的 Subtask。\n\n## Input\n\n第一行三个整数 $n,m$ 和 $C$。\n\n第二行 $n$ 个整数 $a_{1\\dots n}$。\n\n第三行 $m$ 个整数 $b_{1\\dots m}$。\n\n## Output\n\n第一行两个数 $p$ 和 $q$。\n\n[samples]\n\n## Background\n\n**请注意本题并不寻常的时间限制。**\n\n由于 python 自带对于高精度乘法的实现，并且运行效率较高，导致其编写的暴力程序，在一般的时间限制下可以通过绝大部分点。故本题时限开到 $200\\text{ms}$。\n***\n\n黄总是一名计算很强的数学老师，以黄氏约分而闻名。现在他请小 $\\iiint$ A 了这道题。但小 $\\iiint$ **似乎**有点菜，所以求助于你。\n\n## Note\n\n**注释**\n\n$[1]$：[百度百科](https://baike.baidu.com/item/%E6%9C%80%E7%AE%80%E5%88%86%E6%95%B0/2821376?fr=ge_ala)：最简分数，是分子、分母只有公因数 $1$ 的分数，或者说分子和分母互质的分数，又称既约分数。如：二分之一，三分之二，九分之八，八分之三等等。\n***\n**样例解释**\n\n$\\dfrac{540000\\times350000\\times110000\\times130000\\times170000\\times970000}{2000\\times5000\\times1000\\times1000\\times97000\\times17000\\times143000\\times210000}=\\dfrac{9}{10}$，$\\gcd(9,10)=1$\n***\n**数据规模与约定**\n\n**本题采用捆绑测试。**\n\n|Subtask|分值|数据范围|\n|-|-|-|\n|#0|0|同样例|\n|#1|$5$|$1\\le n,m\\le500$，$1\\le a_i,b_i\\le9\\times10^{18}$，$1\\le p,q\\le3\\times10^9$|\n|#2|$5$|$1\\le n,m\\le25000$，$1\\le a_i,b_i\\le9\\times10^{18}$，$1\\le p,q\\le10$|\n|#3|$10$|$1\\le n,m\\le5000$，$1\\le a_i,b_i\\le3\\times10^9$，$1\\le p,q\\le3\\times10^9$|\n|#4|$15$|$1\\le n,m\\le10000$，$1\\le a_i,b_i\\le9\\times10^{18}$，$1\\le p,q\\le3\\times10^9$|\n|#5|$20$|$1\\le n,m\\le25000$，$1\\le a_i,b_i\\le9\\times10^{18}$，$1\\le p\\le3\\times10^9$，$q=1$|\n|#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$|\n|#7|$20$|$1\\le n,m\\le25000$，$1\\le a_i,b_i\\le9\\times10^{18}$，$1\\le p,q\\le3\\times10^9$|\n|#8|$10$|$1\\le n,m\\le10^6$，$1\\le a_i,b_i\\le10^6$，$1\\le p,q\\le3\\times10^9$|\n|#9|$5$|$1\\le n,m\\le10^6$，$1\\le a_i,b_i\\le9\\times10^{18}$，$1\\le p,q\\le3\\times10^9$|\n***\n**提示**\n\n~~高精度狗都不写。~~\n\n本题时限较小且输入量较大，若你认为自己的算法复杂度正确，请尝试优化读写速度。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10383","tags":["2024","O2优化","洛谷比赛"],"sample_group":[["6 8 0\n540000 350000 110000 130000 170000 970000\n2000 5000 1000 1000 97000 17000 143000 210000","9 10"]],"created_at":"2026-03-03 11:09:25"}}