$A=a_1a_2\cdots a_m,B=b_1b_2\cdots b_n$とします。$\displaystyle\frac{P}{Q}=0.a_1a_2\cdots a_m\dot{b_1}b_2\cdots b_{n-1}\dot{b_n}=\displaystyle\frac{1}{10^m}(a_1a_2\cdots a_m+0.\dot{b_1}b_2\cdots b_{n-1}\dot{b_n})$であり、$c=0.\dot{b_1}b_2\cdots b_{n-1}\dot{b_n}$とすると、$10^nc-c=b_1b_2\cdots b_n=B$より$c=\displaystyle\frac{B}{10^n-1}$です。よって、$\displaystyle\frac{P}{Q}=\displaystyle\frac{1}{10^m}\left(A+\displaystyle\frac{B}{10^n-1}\right)=\displaystyle\frac{(10^n-1)A+B}{10^m(10^n-1)}$より$10^m(10^n-1)P=Q\left\{(10^n-1)A+B\right\}$となります。

$P$と$Q$は互いに素なので、$10^m(10^n-1)$は$Q$の倍数です。よって、$Q=2^s\cdot 5^t\cdot u$（$s,t$は$0$以上の整数、$u$は$2,5$と互いに素な自然数）とすると、$m$の最小値は$\max(s,t)$です。また、$10^n-1$は$u$の倍数となるので、これを満たす$n$の最小値を離散対数を用いて求めれば良いです。

計算量は、$m$を求めるのに$O(\log Q)$、$n$を求めるのに$O(\sqrt{Q})$かかるので、全体で$O(\sqrt{Q})$となります。（上記のリンクに載っているコードでは$O(\sqrt{Q}\log Q)$ですが、今回はそれでも十分間に合います。）

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378