A Bangladeshi Contest at SUST（20151212）
UVa 13041
正整数 $P,Q,L$ が与えられるので
\begin{equation} \begin{split}\frac{P}{Q} = \sum_{k=0}^\infty \left( ak^2 + bk + c \right) \left( \frac{1}{10} \right)^{k+1} \end{split} \end{equation}となるような $(a,b,c),\ 0 \leq a,b,c \leq L$ の組の数を求める問題．
一般的に
\begin{equation} \begin{split}S = \sum_{k=0}^\infty f(k) r^k\end{split} \end{equation}は $rS - S$ を計算することにより
\begin{equation} \begin{split}(r-1)S = -f(0) + \sum_{k=0}^\infty (f(k+1)-f(k)) r^k\end{split} \end{equation}になり，$f(k)$ が $j$ 次の多項式だとすると $f(k+1)-f(k)$ は $j-1$ 次の多項式になる．
よって，今は $2$ 次多項式と冪の積なので，上のような操作を $2$ 回やると，普通の等比級数に帰着され解ける．
実際に解くと
\begin{equation} \begin{split}\frac{P}{Q} = \frac{11a + 9b + 81c}{729}\end{split} \end{equation}つまり
\begin{equation} \begin{split}\frac{729P}{Q} = 11a + 9b + 81c\end{split} \end{equation}となる $(a,b,c)$ を探せば良いことになる．
$z = 729P/Q$ が整数でなければ答えはない．
$z$ が整数なら，$z-11a$ が $9$ の倍数となるような $0 \leq a \leq L$ を全て試し，$w = (z-11a)/9 = b+9c$ なる $(b,c)$ の個数を計算する．
これは，$0 \leq b \leq L$ だから，$\max(0, (w-L)/9) \leq c \leq \min(L, w/9)$ と変形すれば $O(1)$ で数えられる．
よって，合計で時間計算量は $O(L)$ ぐらい．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月27日09時13分02秒
Last modified: 2015年12月16日02時00分27秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る
Logged in as: unknown user (not login)