UVa 13041 - Fraction and Sequence

Source

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)$ ぐらい.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月24日15時48分17秒
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)

ログイン: