Codeforces #70 C Lucky Tickets

題意﹕若有一對數 $(p, q)$ 使得 $p\times q = \hat{p} \times \hat{q}$ ，當中 $\hat{x}$ 是指把 $x$ 的十進制倒置並消去前導零，我們則稱 $(p, q)$ 為幸運對。給定 $X_{\max}, Y_{\max}$ ，求一 $x, y$ 對使得對於任意 $1 \le i \le x,\quad 1 \le j \le y$ ， $(i, j)$ 是幸運對的數量至少為 $w$ 。求最小的 $x\times y$ 使得條件成立。

首先需要注意的是若 $(p, q)$ 是一幸運對的話，則有如下公式


$$\frac{p}{\hat{p}} = \frac{\hat{q}}{q}$$


另，只要任意 $p'$ 使得 $\dfrac{p}{\hat{p}} = \dfrac{p'}{\hat{p'}}$ ，則 $(p', q)$ 也是幸運對。因此我們先要留意把 $\dfrac{p}{\hat{p}}$ 化至最簡。設 $\acute{p}$ 和 $\grave{q}$ 為 $\dfrac{p}{\hat{p}}$ 和 $\dfrac{\hat{q}}{q}$ 的最簡化分數，若 $C_{\acute{p}}$ 和 $D_{\grave{q}}$ 分別包含所有 $i$ 使得 $\acute{i} = \acute{p}$ 和 $j$ 使得 $\grave{j} = \grave{q}$ ，則對於任意的 $i \in C_{\acute{p}}$ 和 $j\in D_{\grave{q}}$ ， $(i, j)$ 必為幸運對，而且一共有 $|C_{\acute{p}}||D_{\grave{q}}|$ 個。

因此先計算所有 $|C_x|$ 的值。這個可以在 $O(X_{\max}\log X_{\max})$ 時間內完成。然後先從 $x = X_{\max}, y=1$ 開始，在不斷減少 $x$ 的同時，提升 $y$ 使得總幸運對至少為 $w$ 。留意每增加一次 $y$ ，便會相應增加了 $|C_{\grave{y}}|$ 組幸運對。並且同一時間統計 $D_{\grave{y}}$ 。當再增加 $|C_{\grave{y}}|$ 組幸運對時超過了 $w$ 則停止統計，並更新答案。這個時候已知再增加 $y$ 不會令答案變得更好，因此可以考慮減少 $x$ 。但減少了 $x$ 將會對原本計算現有多少組幸運對有影響。 $x$ 自身可以和 $|D_{\acute{x}}|$ 個數組成幸運對，因此當 $x$ 減少了一的時候，相應的幸運對的數量須減少$|D_{\acute{x}}|$ ，同時為 $C_{\acute{x}}$ 移去 $x$ 。

這個算法可以在 $O((X_{\max} + Y_{\max})(\log X_{\max}Y_{\max}))$ 時間內完成。