题解：P11932 [CrCPC 2024] 平凡的数论题

· · 题解

验题的时候得到的题面没有 \max(a_i,b_i,c_i) 的限制，来写一下这个版本。

直接做出 d=a*b-c，我们需要求出 d 的一个整根。

我们给出一件非常强的事情：d 的所有整根都是 d 最低非零项的因子，证明考虑直接模这个根。

于是直接做质因数分解，我们可以说明最低项是 O(V^2) 的，于是复杂度 O(nd(V^2))。