Last digit

odzさんのエントリを読んで知ったサイト＆問題が面白かったので忙しいはずなのについ考えてしまった。

n choose m の least significant non-zero digit を見つける問題。素因数分解すると大変そうということだったので、パスカルの三角形とか色々考えてみたけど挫折。最終的には次のような感じ：まず、掛け算と割り算をする数の集合から素因数2と5だけに注目して取り出してしまう。そうすると残った値同士の掛け算や割り算は必ず1の位が0にならず、かつ計算を行ったときに次の値が何であるかが1の位同士から一意に決まる(割り切れることがわかっていることと、2と5が無いので掛け算だけでなく割り算も一意に決まるのがポイント)。それができたら、あとは最初に取り出した2と5(10を作りたくないのでの差分だけを)さらに掛けていき、1の位を求めればよいことになる。

Short Coding はやったことないのでよく分かってないがとりあえず短さ優先でやってみて 380B。割り算の結果の表を中で持ってるので頑張ればもう少し短くできる...?