最近のUVa問題集に,約数関連の問題がいくつも出ていました.いままであまり深く考えなかったことだけに,なんとなく嬉しく思ってしまいます.まだまだ身近に色々な面白い問題が残っていることだと.

#10858 Unique Factorization 素因数分解
#10879 Code Refactoring 素因数分解
#10892 LCM Cardinality 最小公倍数

図書館が身近にあって,普段よく利用していますが,約数の求め方についての解説では,除数として2からの整数で割ってみて,割り切れるかどうかを確かめればいい,という書物もあって.びっくりしました.その本に,おまけにBASIC言語のソースプログラムリストが付いたりしています.

そんな方法は数学的解法に過ぎません.計算時間という大事な観点が欠落しています.整数を2からひとつずつ割ってみるというやり方にすると,計算時間は整数1つにつき,その大きさに比例してしまいます.整数の最大値をM,整数の個数をNとすると,全体の計算時間は最悪 O(MN) になります.

時間的速いやり方としては,一旦素因数分解して,個々の素因数のあらゆる組合せから約数を合成するという方法だと思います.問題が簡単過ぎて,約数の求め方を真剣に言及する書物やネット情報はなかなかなく,約数の一覧表をもっとも速い方法で作り出すアルゴリズムを目下考えているところ.

頼りにしているのはつぎの数学定理.

整数 M = paqbrc… と素因数分解できれば,M のすべての約数は
   0 <= x <= a, 0 <= y <= b, 0 <= z <= c, ...
とすることによって漏れなくまた重複なく得られる.

なお,約数の数については,昔の記事にも書きましたが, (1+a)*(1+b)*(1+c)* … というものです.

また,最小公倍数の問題とは,最小公倍数を求めるものではありません.2つの整数 a, b の最小公倍数を LCM(a, b) で表すと,a と b の最大公約数 GCD(a, b) を Euclid 互除法で求めれば,LCM(a, b) = a*b/GCD(a, b) で簡単に求まるからです.

問題にしているのは,最小公倍数の値を N として与えられると,LCM(a, b) = N の a, b ペアの組合せをすべて求めることです.

例えば,最小公倍数が 12 となる整数ペアの組合せは

  (1,12) (2,12) (3,4) (3,12) (4,6) (4,12) (6,12) (12,12)

の8ペアです.なお,a と b の入れ替わったペア,例えば (12,1) はカウントされません.組合せですので.

最小公倍数の値が大きくなると,そのペア数は簡単に求められるかどうか,考えてみたいものです.

Comments are closed.

Post Navigation