ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「アフター・ドット」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

自然数 n に対し、1 ≦ a ≦ n,1 ≦ b ≦ n を満たし、かつ小数で表した a÷b が有限小数となるような自然数の組 (a, b) の個数を F(n) と定義します。
(有限小数…小数点以下の桁数が有限である小数。)

例えば、F(3) = 7 です。
下記の (a, b) の組のうち、有限小数は太字で記した 7 個です。

1÷1=1, 1÷2=0.5, 1÷3=0.33333…
2÷1=2, 2÷2=1,  2÷3=0.66666…
3÷1=3, 3÷2=1.5, 3÷3=1

同様に、F(5)=21,F(10)=68,F(100)=2185 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 104)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針

a÷b が有限小数となるような (a, b) の組の個数を求める問題です。問題文自体はいたってシンプルですが、解き方は一筋縄ではいきません。

単純に思いつく解法は、全ての (a, b) の組を列挙して、a÷b を実際に計算してみるという方法です。ですが、n の上限は 104 という条件です。最大で 104×104=108 個の組をチェックしなければなりません。これでは計算量的に大変ですので、高速化を考えましょう。

そのために必要となるのが、a÷b が有限小数になるってつまりはどういうこと? と考えることです。

実際にいくつかの組で試してみましょう。1÷2=0.5、1÷4=0.25、1÷5=0.5、1÷8=0.125、などは有限小数ですが、1÷3=0.333…、1÷6=0.166…、1÷7=0.142…、などは有限小数ではありません。ここから想像すると、分母が 2、5 以外の約数を持つなら、a÷b は有限小数となりそうです。

ただそれでは十分ではありません。例えば 3÷6 は、分母に 2、5 以外の約数の 3 を持ちますが、3÷6 自体は有限小数です。分子と分母の 3 とが約分で消えるためです。分母が 2、5 以外の因数を持っていたとしても、同じ因数が分子にあれば、a÷b は有限小数となります。

以上の考察をまとめます。a と b が次のように表されれば、a÷b は有限小数となるということです。

分母を一つ固定しよう

では、そのような組 (a, b) の個数はどのように計算すればよいでしょうか。ここでは、始めに、分母 b の値を一つ固定してみましょう。固定した b の値を 2 で割り切れなくなるまで割っていきます。その商を今度は 5 で割り切れなくなるまで割っていきます。こうして得られた商は、上式の b の赤で囲った「2, 5 で割り切れない因数」に相当します。

次に分子 a に目をやります。右端の赤囲みの部分は、いま求めた値と同じです。それに (任意の自然数) を掛けたものが a になるわけですから、そのような a は 1 ≦ a ≦ n の範囲にいくつ存在するかというと、floor(n ÷ (赤囲みの値)) 個だと分かります(floor():小数点以下を切り捨てる関数)。

結局、1 ≦ b ≦ n の範囲で変数 b をループで回して、上記の floor(n ÷ (赤囲みの値)) の値を足していけば、求めるべき答えが得られます。

コード例は以下です(C++)。

#include
using namespace std;

int main() {
int n = 10;
cin >> n;
int answer = 0;
for (int b = 1; b

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP