この重複を防ぐため、次の条件を追加します。$g$は素因数2,5を含まないそうすると、$a$の個数は単純に$g$の倍数の個数として、$b=g2^x5^y$の個数は、$\lfloor\frac{n}{g}\rfloor$以下の、2,5のみを素因数とする数の個数として数えることができます。数式で表すなら次のようになります。$$とは言え、2個目の$\sum$、このままでは手を付けられません。個数を数えることを考えます。「2の指数として適している数の個数」はビット長をそのまま使うことができますので、例えば次の形に直せます。$$※なお、式中のBL()はbit長を表すものとします。ビット長を調べるための計算量を一定だとすると、トータルの計算量は$O(nlogn)$となります。範囲ベースのアプローチ次に。オーソドックスな実装では、5の指数を変化させるところで$logn$の計算量が出てくるわけですが、ここをどうにかできないでしょうか。あれば、「個数」を固定してあげれば、「ある数」というのは連続な区間に収まるはずです。$$実装について、これ単独のものは割愛しますが、最初に区間の情報を調べて保持しておけば、いちいち指数の個数を数える必要がなくなりますから、計算量が$O(n)$に落ちています。区間の情報を調べるのは、単調な関数に対してなので、二分探索が使えます。ハイブリッドなアプローチ上で出てきた式をもう一度見てみます。$$ここで、$q=\lfloor\frac{n}{q}\rfloor$と置いてみます。$$そうすると、$q$がそれなりに大きい値の場合、対応する$g$の数が少ない、すなわち、総和計算におけるループ回数が少なく済むであろうと予測ができます。逆に$q$が小さい値の場合は、同じ$q$に対する$g$の値はたくさんあるにも関わらず、ずっと同じ$sq$を足し続けることになります。あれば、$q$が小さい範囲に対しては、$g$の個数を調べて$sq$と掛け算すれば、わざわざ足し続けなくて済むのではないかと考えてみます。$$という変形になります。この$\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による実装です。1秒以内に計算することができます。)、文字通り桁が違います。終わりに倍数・約数の理解が十分であれば難しくはないと思いますが、色々と考える余地があり、良い試金石になりそうな問題かと思います。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。