Cow Math

最近スランプとかぐだぐだ言ってますが、、

理由の１つに魅力的な問題に見えない、という事があって。

いままではどんな問題でも解くのが楽しかったんだけど、

"簡単すぎ"とか"プログラム書くだけ"とか言う問題が嫌になってきて。


でも今日久々に(最近やってなかったから久々なだけかもしれんけど)

楽しい問題に出会いました、、それが pku2132 Cow Math

問題自体はちょと説明が面倒なんですが、


25個の街と、それら任意の2都市をつなぐ道路が与えられます。

各道路には道路番号(重複しうる)が与えられていて、

Bessieは都市1から都市2に行きたいのですが、

"都市1から都市2に行く間に他の都市を通ってもよいが、

同じ都市を2回通ってはいけない"という条件が与えられています。

Bessieは、最大公約数を計算するのが大好きな子なので、

都市1から都市2まで行く途中で通った道路の番号の、

最大公約数を計算して覚えて行きます(笑)


さてここで問題です。Bessieが都市1から都市2に行くには、

沢山の行き方が存在します。それぞれに行き方に対して、

経由した道路番号の最大公約数が存在する訳ですが、

それらの最小公倍数はいくつでしょうか。


という問題です。説明が下手な上に問題がややこしいのでカオスw

最大公約数とか最小公倍数とか出てきて"うわー、、嫌な問題"

って思ったのですが、思いついてみればすごく綺麗な解法があって。

こういう素敵な解法を思いついた瞬間が気持ちいいんだよなぁーって、

改めて感じました。さてここを見たプログラマの方、思いつきますかね？w



説明のためにちょと簡単化した部分とかあるので、

問題解く人はちゃんと問題文を読んでくださいな。



で、明日はニコニコ技術部 京都勉強会を見学してきます。

なんかいい刺激があると嬉しいな、、楽しみ楽しみw