- 互いに素な整数の組の列挙

互いに素な整数の組の列挙

Euler296のThreadから

問題：互いに素な正整数の組x,yであって、x+y<=n (など、x,yについて単調な何らかの条件)を満たす組を順序不問で全て列挙せよ

この問題は愚直にやるとgcdのlogがついてO(ans*log)になる。
Stern-Brocot treeを使うとgcdが不要になりO(ans)になるが、空間O(n)などになる
Stern-Brocot treeを使うアプローチで空間O(1)にすると時間にlogがつくと思う

実は時間O(ans)空間O(1)でできます

ユークリッドの互除法を引き算だけでやるような次のようなアルゴリズムを考えます


def gcd(x,y):
  # assume x  while x!=y:
    y-=x
    if x>y:
      x,y=y,x
  return x

これを逆回しにします


def dfs(x,y):
  if x+y>n: return
  print(x,y)
  dfs(x,x+y)
  dfs(y,x+y)

このDFSのなす木をぐっと睨みます

できました


def gen():
  x,y=0,1
  while x+y!=2:
    if x>y:
      # 青,赤で上へ
      x,y=y,x-y
    else:
      # 青,赤で下へ
      x,y=y,x+y
      while x+y<=n
        print(x,y)
        # 赤で下へ
        y+=x
      # 赤で上へ
      y-=x

<< 前のページ | ホーム | 次のページ >>

コメントの投稿

トラックバック

この記事にトラックバックする(FC2ブログユーザー)

<< 前のページ | ホーム | 次のページ >>