ユークリッドの互除法

ってのは有名なので聞いたことあるはずー、、というか中学とかでやったような(？)

一応書いとくと、「246と138の最大公約数(gcd)は？」って聞かれたときに、

gcd(246,138)=gcd(246%138,138)=gcd(108,138)=gcd(108,138%108)=gcd(108,30) ...

って求めていく方法です。(上の式でa%bはaをbで割ったあまり、って意味です。)



んでー、、今日問題を解いてて、こんな問題を見つけたのです。

icpc関係の方はtryしてみてね(笑)

http://projecteuler.net/index.php?section=problems&id=134


まぁこの問題は、与えられたp1,p2に対して、

(1000*n+p1)%p2=0

みたいな方程式をみたす最小の自然数nを求める問題になるのですが、

この方程式は中学やら高校やらで習った普通の方程式のように簡単には解けないのです。

何故かというと、、方程式の中に％、つまり「割り算のあまり」が入っているから。

まぁ詳しいことを説明すると面倒なので省略しますが、、

こういう式は変形だけで解ける式ではなくて、

nに1を入れて、割り切れたらn=1が答え。

割り切れなかったら、次はnに2を入れて、割り切れたらn=2が答え。

割り切れなかったら、次はnに3をいれて…

みたいな感じで解かないといけないのです。

いや、訂正。

つい2時間前までそうやって解かないといけないと思っていたのです。


でも上に挙げた問題、こうやって解いたらあまりに時間がかかってどうしようもなくて。

何かいい方法ないかなぁとか思って検索して見たのです。グーグル検索。

頑張って調べましたとも。日本語入れたり英語入れたりしてみましたとも。

10個ぐらいキーワード入れたところでさすがグーグル、見つけてくれました。

http://mathworld.wolfram.com/ModularInverse.html


このページの中に「ユークリッドの互除法で解けるよ☆」って書いてあって、

でも「ユークリッドの互除法って最大公約数を求める奴だよなぁ」とか思って、

今度はwikipediaを引いてみました。

http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95


そしたら何か、「拡張された互除法」とか書いてあるじゃないですか。

んー、、何か聞いたことあるような。

実はすっかり忘れてたんですが、、ユークリッドの互除法には拡張版があって、

(といってもほとんど普通の互除法と同じ)それを使えって話だったんです。

んでこんどは「拡張ユークリッドの互除法」で検索して、、

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html

こんなページを見つけて。。どうやら新潟大学のページみたいですw


これを使ったプログラムを書いたら、一番初めに載せた問題も高速に解けました、、

互除法を使う前は5分かかっても解けなかったのが、なんと0.08秒で解けるようになったというw


んー、、拡張ユークリッドの互除法の話をするつもりでブログを書き始めたのに

その前後の話で書きすぎてしまったなぁ。。

気になる方は上の新潟大学のページを読むか、、miracまで聞いてくださいw


ぐだぐだになったので無理やりまとめてみると、、

(1000*n+p1)%p2=0

みたいな方程式はO(log p2)ぐらいで解ける、と。

n=1の場合、とかn=2の場合、とかがりがりやらなくても解ける、と。

しかもそれはユークリッドの互除法をほんの少しいじるだけでできる、と。

んー、、さらにぐだぐだになった感が否めないな。。

まぁまた今度暇だったら書きます☆



前にプログラムの日記書いたときから25問ぐらい解いた形跡があるので、

目標の200問まであと156問!!　国内大会まであと31日!!