ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。数学はじめにCodeIQというところでプログラミング問題「アフター・ドット」に解答しましたので、ネタバレです。範囲で、有限小数となる分数$\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を完全に除去」というところが曲者です。試し割りしていたのでは、文字数的に全然です。10000$という条件を思い出してみます。すると$n$以下の$b$に関して素因数2は高々$2^{13}$、5は$5^5$で収まることが分かります。いうことは、十分に大きい$2^x5^y$と$b$の最大公約数をとって$b$を割ってあげれば、それで「素因数2,5を完全に除去」することができます。いうことで、実装したのがRuby(50)です。$$という理屈になっています。reduceの使い方が邪悪な気もしますが。総和の元として使われ、$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$の個数を数えれば、トータルの個数も計算できるということになります。そのままでは重複してカウントしてしまう懸念があります。