拡張ユークリッドの互除法についての話です。
きっかけは、AIZU ONNLINE JUDGEの整数論(NTL)からの"Extended Euclid Algorithm"の出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E
まずユークリッドの互除法とは、Wikipediaによれば...
>2 つの自然数の最大公約数を求める手法の一つである。
https://ja.wikipedia.org/wiki/ユークリッドの互除法
>2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。
>この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
>明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。
小学校の授業では、ちょうど約数を習っているところです。
いや、普通の小学校に通っている普通の小学生だから、それで普通です。
その方が楽だし、色々な意味で。
ってか、短縮授業は今月までっぽい、関係ないけれど。
次に、拡張された互除法については...
>整数 m, n の最大公約数 (英: Greatest Common Divisor) を gcd(m,n) と表すときに、（拡張された）ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解となる整数 x, y の組を見つけることができる。
>特に、m, n が互いに素（最大公約数が 1）である場合、mx + ny = 1 の整数解を (x, y) とすると、mx + ny = c は任意の整数 c に対して整数解 (cx, cy) をもつことが分かる。
そして、AIZU ONNLINE JUDGEの整数論(NTL)からの"Extended Euclid Algorithm"の出題では...
「与えられた２つの整数 a、b について ax+by=gcd(a,b) の整数解 (x,y) を求めてください。ここで、gcd(a,b) は a と b の最大公約数です。」
わっ、そっくりそのままでした。
ってか、そうゆうことかー。
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #NTL_1_E : Extended Euclid Algorithm
/* Aizu Online Judge in C++ #NTL_1_E : Extended Euclid Algorithm https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; template<typename T> T EGCD(T a,T b,T &x,T &y){ if(b==0){ x=1; y=0; return a; }else{ T l=EGCD(b,a%b,y,x); y-=(a/b*x); return l; } } int main(void){ long long a,b,x,y; cin>>a>>b; EGCD(a,b,x,y); cout<<x<<" "; cout<<y<<endl; return 0; }
それから、計算量について...
>割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の約 5 倍繰り返せば、最大公約数に達する（ラメの定理）。
>最大公約数を求めるのに、素因数分解してみればいいと考える人がいるかもしれないが、この定理は素因数分解を用いるよりもユークリッドの互除法による方がはるかに速いということを述べている。
>実際、計算複雑性理論においては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。
>入力された2つの整数のうち小さいほうの整数 n の桁数を d とすれば、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められる。
>桁数 d は O(log n) なので、ユークリッドの互除法では O(log n) 回の除算で最大公約数が求められる。
ここで、『計算複雑性理論』については...
>計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。
>計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
>「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。
なるほど、面白そう、ってか、こうゆうことねー。
>計算複雑性理論は計算可能関数の計算の複雑さを扱う。
>計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
>具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。
あっ… （察し）
で、具体的には...
>計算複雑性理論で扱う問題とは、ある一連の問いの集合があり、各問いは有限長の文字列で表され、与えられた問いに対して解を求めて出力する計算問題である。
>問題に属する個別の問いをインスタンスと呼ぶ。
これって、もうすでに競技プログラミングに包含されているような気がしたけれど、そもそも競技プログラミングと、それで取り扱う範囲が未定義だし…？
大学とかで取り扱う場合とか、学問的に言えば、これらはまるっと『コンピュータサイエンス』ってことになるのかな？
でも、現実に「僕の趣味は、コンピュータサイエンスです」って言っても、何も伝わらないだろうなー。
だからと言って、「プログラミング」って言うと、ゲームとかアプリを開発するようなイメージがあるらしくて、「あ、ごめん、ちょっと違うんだよねー」ってなっちゃうし、「じゃなくて競技的な、数学寄りなヤツ」ってなります、僕の場合は。
つまり僕がやっているのは、「じゃなくて競技的な数学寄りのプログラミング」の学習です。
だから、「みんなに使ってもらえるようなアプリを開発したいです！」とか言わないし、「何かの賞をとって親孝行がしたいです！」なんて思いません、思えません。
あのー…強いて言うなら「昨日解けなかった問題を、今日は解けるようにしたいなー」って感じです。
それだけです、つまらないだろうけれど。
まぁ、ここには書けないこともあるし、やれるだけのことをやっています、普通に毎日ね。
さて、具体的には...
>計算問題の複雑性（または計算量）とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。
直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。
>しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。
>そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。
競技プログラミングで言うと、TLEとかMLEで示されます、デバッグしよー。
終わりに、『イントラクタブル』について...
>理論上計算可能な問題であっても、実際に解くことができない問題をイントラクタブル (英: intractable, 手に負えない、処理しにくい) であるという。
>「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。
>イントラクタブルな問題として知られているものとしては、EXPTIME完全な問題がある。
>NP が P と同じでなかった場合、NP完全な問題もイントラクタブルだということになる。
わかりやすい例としては...
>指数関数時間の解法がなぜ実際には使えないかを考えるため、2n 回の操作を必要とする問題を考える（n は入力のサイズである）。
>比較的小さな入力数 n = 100 のときについて、1秒間に 1010（10 ギガ）回命令を実行できる計算機を想定すると、その問題を解くには約 4 × 1012 年かかる。
>指数関数時間あるいは指数時間とは、計算理論において指数関数を用いてあらわされる計算時間。
>解くべき問題のサイズ n に対して処理時間が多項式時間では収まらず指数関数的に増加してしまう計算方法を指す。
>計算複雑性理論では指数関数時間で解ける判定問題のクラスのことをクラス EXPTIME（あるいは EXP）という。
はい、よくわかりましたー。
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/
