对询问的模数分解，对每个素因子 $p$，将 $a_i$ 和 $b_i$ 中所有 $p$ 的因子全部提出，$b_i$ 剩余的部分就可以求逆元。最后如果有一个素因子的指数为负则无解，否则乘上对应的次数即可。
时间复杂度 $O(k\cdot (M^{1/4}+(n+m)\log (M+a+b)))$。
QOJ.ac
QOJ
Discussion #141 for Problem #7230. Fraction Factory
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:30:57
Last updated: 2025-12-12 23:31:01
题解
Comments
No comments yet.