对询问的模数分解，对每个素因子 $p$，将 $a_i$ 和 $b_i$ 中所有 $p$ 的因子全部提出，$b_i$ 剩余的部分就可以求逆元。最后如果有一个素因子的指数为负则无解，否则乘上对应的次数即可。
时间复杂度 $O(k\cdot (M^{1/4}+(n+m)\log (M+a+b)))$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.