ツリーの中の距離 横へな2017.2.4 問題

問題の概要

数がある。
数には子供がいる。子供は「その数の約数+1、ただし、2より大きくその数より小さいもの」だ。
例えば。50 の約数は{ 1, 2, 5, 10, 25, 50 }。
約数+1 は、{ 2, 3, 6, 11, 26, 51 }。
これらのうち、2よりも大きく、50よりも小さいものは { 3, 6, 11, 26 } なので、これが 50 の子供たち。
子供にはまた子供が、その子供にはまた子供がいたりいなかったりして、ツリーになる。
で。
ツリーの中にある数の距離を「親子関係の線で辿ったときの線の本数の最小値」で定義する。
たとえば、根が 50 のツリーの中では、

• 26 と 5 の距離は 3
• 4 と 3 の距離は 1
• 8 と 50 の距離は 3
• 11 と 3 の距離は 2
• 5 と 4 の距離は 6

となる。

で。ツリーの根となる数と、ツリー内にある2つの数を与える。2つの数の距離を計算せよ。

入力

入力は
50:6,3
こんな感じ。
コロンの前が根の値。コロンの後にコンマ区切りで2つの数。

出力

出力は簡単。2数の距離を 10進数で出せば良い。

先ほどの入力の場合、線をたどればわかる通り、
1
と出力すればよい。

補足

• ツリーに含まれない数が指定されることはない。
• 2つの数が等しいことはない。
• 同じ数でも祖先が違えば別のノードです。
• 不正な入力に対処する必要はない。
• 実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。
• この問題は2017年2月4日に開催される オフラインリアルタイムどう書くE11 の問題です。イベントについては Doorkeeper のページ の方を御覧下さい。

サンプルデータ

C/C++/Java 用のテストデータ