AOJ 1131 - Unit Fraction Partition - ツバサの備忘録

解法

DFSで答えを探します。
まず、分母の値が小さいものから順番に使用していくとします。そして、以下の情報を持ちながら探索していきます。

一番最後に使用した単位分数の分母の値 $r$
現在の総和(分母、分子) $m,c$
現在いくつの単位分数を利用したか $s$

現在の総和は、分母を最小公倍数にしたりする必要はなく、使用した単位分数の分母を全て掛け合わせたものを分母にしていれば大丈夫です。これにより、 $a$ を超えたかどうかの判定が簡単になります。初期は、 $r = m = 1,c = s = 0$ となります。

さて、ある状態にたどり着いたとき、行う操作は2つあります。次に単位分数を追加した場合に、目標の $p/q$ にたどり着くパターンと、 $p/q$ 未満になるパターンです。

単位分数を追加したときに、 $p/q$ と一致するパターン
$\frac{c}{m} + \frac{1}{x} = \frac{p}{q}$
となる必要があるので、 $x$ に関する式に直すと、
$x = \frac{mp-cq}{mq}$
となり、これが $xm \leqq a, x \geqq r$ を満たす正整数になればよいです。
ということで、 $(mp-cq) \% mq = 0,xm \leqq a, x \geqq r$ を満たすときに答えのカウントを1増やせばよいです。
単位分数を追加したときに、 $p/q$ 未満となるパターン
次に使用する単位分数の分母は、次の条件を満たす必要があります。
$\frac{c}{m} + \frac{1}{x} \lt \frac{p}{q}$
$mx \leqq a$
このときに、次の状態は、
分母の最大値: $x$
総和の分母: $mx$
総和の分子: $cx+m$
使用した個数: $s+1$
となります。
提出したコードには、もう一つ、「これ以降 $1/x$ を全て追加しても[p/q]に届かないならば探索を中断」という条件も加えていたのですが、この部分を消去しても十分間に合いました。