はじめに

CodeIQというところでプログラミング問題「アフター・ドット」に解答しましたので、ネタバレです。

問題

入力 n ( $1\le n\le 10000$ ) に対して、$1\le a,b\le n$ の範囲で、有限小数となる分数$\frac{a}{b}$の個数を出力するものです。

解説

golf方向と高速化方向と、両方で考えました。実際の時系列通りではないのですが、先にgolf版から行きたいと思います。

golf版

$\frac{a}{b}$が有限小数ということは、$b$から素因数2,5を完全に除去した$b'$に対して、$a$が$b'$で割り切れることに他なりません。$a$の個数については、1つ1つ$a$の値を試さずとも、$\lfloor\frac{n}{b'}\rfloor$を計算すれば済みますから、そこから総和をとればよいことになります。

しかし、この「素因数2,5を完全に除去」というところが曲者です。試し割りしていたのでは、文字数的に全然です。

ただここで、$n\le 10000$という条件を思い出してみます。そうすると$n$以下の$b$に関して素因数2は高々$2^{13}$、5は$5^5$で収まることが分かります。
ということは、十分に大きい$2^x5^y$と$b$の最大公約数をとって$b$を割ってあげれば、それで「素因数2,5を完全に除去」することができます。

ということで、実装したのがRuby(50)です。

p (0..n=gets.to_i).reduce{|s,b|s+n*b.gcd(80**5)/b}

$$ b'=\frac{b}{gcd(b,80^5)}\Rightarrow \lfloor\frac{n}{b'}\rfloor=\lfloor\frac{n\times gcd(b,80^5)}{b}\rfloor $$

という理屈になっています。

ちょっとreduceの使い方が邪悪な気もしますが。(0..n).reduce{}とすると、最初の 0 が総和の元として使われ、$b=0$に対してのブロック実行がなされません。つまり(1..n).reduce(0){}と同じ効果があります。

…ただ、最短で49文字が出ていてちょっと足りないんですよね…。

高速化版

オーソドックスなアプローチ

「有限小数」の条件を改めて考えてみて、今度は。$a,b$の最大公約数$g$に着目してみます。そうすると、$\frac{a}{b}$は$g$で約分して既約分数にできますから、次が有限小数となる条件となります。

$g$を$a,b$の最大公約数とした時、$\frac{b}{g}$の素因数は2,5のみ

ということは、個々の$g$毎に$a,b$の個数を数えれば、トータルの個数も計算できるということになります。

ただし、そのままでは重複してカウントしてしまう懸念があります。
例えば、$g=3, a=8g, b=20g$ と $g=12, a=2g, b=5g$ のように。この例はいずれも$a=24,b=60$ に相当します。

この重複を防ぐため、次の条件を追加します。

$g$は素因数2,5を含まない

そうすると、$a$の個数は単純に$g$の倍数の個数として、$b=g2^x5^y$の個数は、$\lfloor\frac{n}{g}\rfloor$以下の、2,5のみを素因数とする数の個数として数えることができます。数式で表すなら次のようになります。

$$ \sum_{1\le g\le n,\,2\nmid n,\,5\nmid n}^{} \bigl( \lfloor\frac{n}{g}\rfloor\times\sum_{2^x5^y\le \lfloor\frac{n}{g}\rfloor} 1 \bigr) $$

とは言え、2個目の$\sum$、このままでは手を付けられません。そこでオーソドックスに、5の指数 ( 数式中の$y$ ) の値を変化させつつ、2の指数として適している数 ( 数式中の$x$ ) の個数を数えることを考えます。「2の指数として適している数の個数」はビット長をそのまま使うことができますので、例えば次の形に直せます。

$$ \sum_{1\le g\le n,\,2\nmid g,\,5\nmid g}^{} \bigl( \lfloor\frac{n}{g}\rfloor\times\sum_{5^y\le \lfloor\frac{n}{g}\rfloor} BL(\lfloor\frac{n}{g5^y}\rfloor) \bigr) $$

※なお、式中のBL()はbit長を表すものとします。

ビット長を調べるための計算量を一定だとすると、トータルの計算量は$O(nlogn)$となります。

範囲ベースのアプローチ

次に。オーソドックスな実装では、5の指数を変化させるところで$logn$の計算量が出てくるわけですが、ここをどうにかできないでしょうか。

…良く考えると、「ある数以下の$2^x5^y$の形の数の個数」というのは、単調増加 ( 非減少 ) な関数になるはずです。であれば、「個数」を固定してあげれば、「ある数」というのは連続な区間に収まるはずです。

例えば、「ある数以下の$2^x5^y$の個数が6個」であれば、ある数としては 11～15 の範囲に対応します。( $2^x5^y$の数に該当するのは、1,2,4,5,8,10、次の16は含まれない )

ということで、個数$s $に対応する区間を$I(s)$とすると、

$$ \sum_{s}^{}\sum_{2\nmid g,\,5\nmid g,\,\lfloor\frac{n}{g}\rfloor\in I(s)} s\lfloor\frac{n}{g}\rfloor\,\,\,\,\,\,(\,t\in I(s)\Leftrightarrow t以下の2^x5^yの形の数の個数がs個) $$

実装について、これ単独のものは割愛しますが、最初に区間の情報を調べて保持しておけば、いちいち指数の個数を数える必要がなくなりますから、計算量が$O(n)$に落ちています。なお、区間の情報を調べるのは、単調な関数に対してなので、二分探索が使えます。

ハイブリッドなアプローチ

上で出てきた式をもう一度見てみます。 $$ \sum_{s}^{}\sum_{2\nmid g,\,5\nmid g\,\lfloor\frac{n}{g}\rfloor\in I(s)} s\lfloor\frac{n}{g}\rfloor\,\,\,\,\,\,(\,t\in I(s)\Leftrightarrow t以下の2^x5^yの形の数の個数がs個) $$

ここで、$q=\lfloor\frac{n}{q}\rfloor$と置いてみます。 $$ \sum_{s}^{}\sum_{2\nmid g,\,5\nmid g,\,q=\lfloor\frac{n}{g}\rfloor\,\,q\in I(s)} sq\,\,\,\,\,\,(\,t\in I(s)\Leftrightarrow t以下の2^x5^yの形の数の個数がs個) $$

そうすると、$q$がそれなりに大きい値の場合、対応する$g$の数が少ない、すなわち、総和計算におけるループ回数が少なく済むであろうと予測ができます。が、逆に$q$が小さい値の場合は、同じ$q$に対する$g$の値はたくさんあるにも関わらず、ずっと同じ$sq$を足し続けることになります。

であれば、$q$が小さい範囲に対しては、$g$の個数を調べて$sq$と掛け算すれば、わざわざ足し続けなくて済むのではないかと考えてみます。半開区間$(d,u]$に対して、この区間に含まれる、2,5の倍数以外の数の個数を$\sigma(d,u)$とすると、

$$ \sum_{s}^{}\sum_{q\in I(s)} sq\sigma(\lfloor\frac{n}{q+1}\rfloor,\lfloor\frac{n}{q}\rfloor) $$

という変形になります。なお、この$\sigma(d,u)$とは、$\phi(x)=x-\lfloor\frac{x}{2}\rfloor-\lfloor\frac{x}{5}\rfloor+\lfloor\frac{x}{10}\rfloor$を用いて、$\sigma(d,u)=\phi(u)-\phi(d)$と表すことができます。

実は、この$q$ベースの総和だけで全部計算することもできるのですが、区間$I(s)$というのは、$s$が大きくなるにつれてどんどん広くなりますから、$s$が大きな領域では計算量的に不利になります。逆に、前の$g$ベースの総和では、$s$が小さな領域で計算量が多くなっているのでした。

それであれば、お互いが計算量的に有利な部分で計算を分けてハイブリッドにやれば良い、ということです。大体同じ計算量になるように分けると、$O(\sqrt{n})$にまで落とせます。

実装

というわけで、C99による実装です。CodeIQの実行君では、f(1,500,000,000,000,000) を1秒以内に計算することができます。オーソドックスなやり方だとせいぜい億程度でしょうから ( Rubyであれば数百万 )、文字通り桁が違います。

終わりに

倍数・約数の理解が十分であれば難しくはないと思いますが、色々と考える余地があり、良い試金石になりそうな問題かと思います。

ange1のブログ

「アフター・ドット」問題解答 ( CodeIQ )