『[NOIP2009 提高組] Hankson 的趣味題』題解

「[NOIP2009 提高組] Hankson 的趣味題」題解

原題目連結：Link。

題意：有 \(n\) 次詢問，給出 \(a_0,a_1,b_0,b_1\) 四個數。求滿足 \(\gcd(x,a_0) = a_1\)，\(\text{lcm}(x,b_0) = b_1\) 的 \(x\) 的數量。

通過 \(\text{lcm}(x,b_0) = b_1\)，我們可以知道 \(x\) 一定是 \(b_1\) 的因數。是以我們可以枚舉 \(b_1\) 的因數，再檢驗即可。時間複雜度為 \(O(n \sqrt{b_1} \log b_1)\)，然後呢？

就這樣被艹過去了……代碼如下：