オイラーの関数φ(n)の値が与えられた時の、nを求める問題。つまり、

  φ(n)=x のxに対し、n=φ-1(x)

を考える。

整数の素因数分解と同様、逆関数の計算はとても難しい。だから問題として出されているかもしれない。

1. 元問題 — UVa #11073 – Euler’s Totient Function
  xの値の範囲は 1<=x<=1000000000。
nの値が複数ある場合、昇順で表示する必要もある。

2. 実例
  x=2に対して、n=3,4,6
  x=4に対して、n=5,8,10,12
  x=583925760に対して、書ききれないが、異なるnは19639個存在する。

3. 考え方
 xの値が小さければ、例えば、100万までなら、φ(n)の値をすべてテーブルに計算登録し、xでlookupする方法も考えられるが、10億もの巨大xではこの方法は無理だろう。

幸い、元問題の入力値xの個数はそれほど多くないらしく、素直に個々にxの逆関数を計算していくことにした。

自分では以下の漸近式を使った。

p11073.jpg

つまり、2から約32000(10億の平方根)までのの素数をひとつひとつ持ってきて、xを(p-1)*pkで割り切れるかどうかを確かめる。割り切れるのであれば、x/((p-1)*pk)を新たなxとして、その逆関数を再呼び出して分解していく。計算できたnをひとつひとつテーブルに登録し、最後にソートをかけ画面出力する。

ちなみに、本方法では、途中で打ち切ることがあっても、nの値がダブって算出されることはない。

なお、x=1に対しては、n=1,2と結果表示し、他の奇数のxに対しては、解がなしと表示する。

4. 実例で説明
 基本的な考え方は上記の通りだが、細かいところについては以下の実例をよく見て、理解すること。

x=4について考える。

(1-1) まず最初の素数p=2を持ってくる。k=0とし、(p-1)*pkを見ていく。なお、k=1については(1-2)の所、k=2については(1-3)の所で調べる。
  p=2, k=0では、(p-1)*pk=1, pk+1=2, x/((p-1)*pk))=4になり、φ-1(4)→2*φ-1(4)になる。
 (1-1-1) 素数2は上で既に使ったので、ここでは次の素数3で調べる。p=3,k=0のもとでは、(p-1)*pk=2, pk+1=3, 4/((p-1)*(pk)=2になり、2*φ-1(4)→6*φ-1(2)になる。
  (1-1-1-1) つぎの素数5で調べる番になっているが、2を(p-1)*pk=4*5kで割り切ることはありえないので、一旦ここで打ち切り。
 (1-1-2) つぎの素数5で調べる。p=5,k=0のもとでは、(p-1)*pk=4, pk+1=5, 4/((p-1)*(pk)=1になり、2*φ-1(4)→10*φ-1(1)になる。φ-1(1)は1であるので、最初のnが見つかり、n=10。
(1-2) (1-1)の続きをやる。つまり、p=2, k=1。
  p=2, k=1では、(p-1)*pk=2, pk+1=4, x/((p-1)*pk))=2になり、
φ-1(4)→4*φ-1(3)になる。
 (1-2-1) 次の素数3で調べる。p=3,k=0のもとでは、(p-1)*pk=2, pk+1=3, 4/((p-1)*(pk)=2になり、
4*φ-1(2)→12*φ-1(1)になり、2番目のn=12がみつかる。
(1-3) (1-2)の続きをやる。つまり、p=2, k=2。
  p=2, k=2では、(p-1)*pk=4, pk+1=8, x/((p-1)*pk))=1になり、
φ-1(4)→8*φ-1(1)になり、3番目のn=8がみつかる。

(2-1) 2番目の素数p=3を持って来て調べる。
  p=3, k=0では、(p-1)*pk=2, pk+1=3, x/((p-1)*pk))=2になり、
φ-1(4)→3*φ-1(2)になるが、つぎの素数5ではそれ以上nを見つけることはないので、打ち切る。

(3-1) 3番目の素数p=5を持って来て調べる。
  p=5, k=0では、(p-1)*pk=4, pk+1=5, x/((p-1)*pk))=1になり、
φ-1(4)→5*φ-1(1)になり、4番目のn=5がみつかる。

ということで、なかなか理解するのは大変かもしれないが、個々の素数をつぎつぎと持ってきてテストし、つぎの深いステップでは、同じ素数は使ってはいけないところが味噌。また、同じステップのところでは、kの値も0からインクリメントして調べる。いわば、3次元的に調べるイメージになる。

p11073-1.jpg

5. 結果
あまりよい計算方法がないらしく、素数をひとつひとつで確かめていき、効率の面を心配していた。結果的にランク1位の実行速度になり、皆も相当苦労していたのだなと実感した。

まだまだ研究余地の残っている問題だと思う。

Comments are closed.

Post Navigation