這題基本上是數論 + 二分搜尋的整合題，只要能求得以下函數的值再搭配二分搜尋就好：
$$G(p, x) = |L(p, x)|, L(p, x) = \{y\ |\ y \leq x\ \&\ y \in L(p)\}$$
白話一點來說，$L(p, x)$ 就是 $L(p)$ 中比 $x$ 小的數值所成的序列，因此 $G(p, x)$ 就是比 $x$ 小的數值中有多少個跟 $p$ 互質。
接著，我們就可以利用二分搜尋的方式在 [1, inf] 中去尋找 $M$ 使得 $G(p, M) = k + G(p, x)$，而 $M$ 就是我們要的答案。因為對任意正整數 $x_1, x_2, G(p, x_1) \leq G(p, x_2)\ if\ x_1\leq x_2$
因此接下來我們就專注在怎麼找出 $G(p, x)$ 即可。而這個值可以簡單的利用排容原理 (inclusion-exclusion principle) 算出來：
令 $x = p_1 ^ {o_1} \times p_2 ^ {o_2} \times \ \dots \ \times p_m ^ {o_m}$，則
$$G(p, x) = p - \sum_{i=1}^{m} \lfloor{\frac{p}{x_i}}\rfloor \quad + \quad \sum_{i=1}^{m} \sum_{j=j+1}^{m} \lfloor{\frac{p}{x_i \ x_j}}\rfloor \quad - \quad \dots$$
上面那個式子可以利用莫比烏斯方程式 (Möbius function) 改寫：
$$G(p, x) = \sum_{d|p} \mu(d) \times \lfloor{\frac{x}{d}}\rfloor$$
實作在此：
[後記]
當初本來想要用 Euler Totient Function 來解，雖然有找到下面這個 Lemma：
Lemma: 令 $x = d \times p$，其中 $d$ 為正整數，則 $G(p, x) = d \times \phi(p)$，其中 $\phi$ 為 。
不過問題會出在當 $x = p \times d + r,\ 0 < r < p$，此時 $G(p, x) = d \times \phi(p) + \phi(p, r)$，其中 $\phi(p, r) = |\{n\ |\ n \in \phi(p)\ \&\ n < r\}|$，也就是 $\phi(p)$ 中跟 $p$ 互質且比 $r$ 小的個數。
後來 Google 找了一陣子找不到數論中有什麼方法可以算 $\phi(p, r)$，因此最後還是得回歸排容原理來算 = =...上面的實作雖然也有把這方法做出來，但說實在的還比不用更慢...
沒有留言:
張貼留言