Day 149-Q5 | Farey数列の逐次生成

問題

正整数Nが与えられる。Farey数列F_N（0以上1以下、分母$N$以下の既約分数を昇順に並べた数列）を、隣接項からの直接計算のみで生成せよ（ソートやgcdによる既約判定は使わない）。

生成規則

最初の2項: $a/b=0/1,\ c/d=1/N$（$N=1$なら$0/1,1/1$）。
次の項: $k=\lfloor (N+b)/d \rfloor$、$next_c=k\cdot c - a$、$next_d = k\cdot d - b$。
$c/d$を出力し$(a,b)\leftarrow(c,d)$、$(c,d)\leftarrow(next_c,next_d)$と更新。$c\le N$の間繰り返す。

制約

$1 \le N \le 8$

gcd判定・ソート禁止

出力は既約分数のみ（自動的に保証される）

入出力例

入力例1

出力例1

11
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

入力例2

出力例2

2
0/1
1/1

概念図：F_5 の数直線上の配置と生成順

ヒント（段階的開示）

ヒント1（方向性）

Farey数列の隣り合う2項$a/b,c/d$は必ず$bc-ad=1$を満たす。この関係を保ったまま「次の1項」を一発で計算できれば、既約性のチェックもソートも要らない。

ヒント2（アプローチ）

連続する3項$a/b,c/d,e/f$のとき$e=k\cdot c-a,\ f=k\cdot d-b$という形で書け、$k$は「$f$が$N$を超えない最大の整数」として$k=\lfloor(N+b)/d\rfloor$で求まる。

ヒント3（誘導）

def farey_sequence(N):
    a, b = 0, 1
    c, d = 1, N
    seq = [(a, b)]
    while c <= N:
        seq.append((c, d))
        k = (N + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
    return seq

模範解答 (Python)

import sys


def farey_sequence(N):
    a, b = 0, 1
    c, d = 1, N
    seq = [(a, b)]
    while c <= N:
        seq.append((c, d))
        k = (N + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
    return seq


def main():
    N = int(sys.stdin.read().split()[0])
    seq = farey_sequence(N)
    out = [str(len(seq))]
    for p, q in seq:
        out.append(f"{p}/{q}")
    print('\n'.join(out))


main()

Step-by-Step 解説

1最初の2項を決める
$N\ge2$なら最初の2項は必ず$0/1,1/N$。$N=1$なら$F_1=[0/1,1/1]$そのもの。

2判別式$bc-ad=1$を利用
隣接2項は常にこの関係を満たす。次の項もこの関係を保つ必要があり、かつ「$f$は$N$を超えない最大の分母」という条件から$k$が一意に定まる。

3$k=\lfloor(N+b)/d\rfloor$の導出
$f=k\cdot d-b\le N$を$k$について解くと$k\le(N+b)/d$。整数なので最大値は床関数。

4終了条件
$c\le N$の間ループし、$c/d=1/1$を出力した時点で自然に終了する。

よくあるミス

ミス	原因	正しい書き方
最初の2項を固定値にしてしまう	$N$に依存することを見落とす	2項目は必ず$1/N$（$N=1$は例外）
$k$を$N//d$で計算	漸化式の導出を誤り$b$の寄与を忘れる	$k=(N+b)//d$を正確に使う
終了条件を項数で判定	項数を事前に知らずに実装しようとする	$c\le N$を条件にすれば自然に止まる
既約でない分数が混ざると疑いgcdで後処理	漸化式が既約性を自動保証することを信じていない	この漸化式の生成結果は常に既約（追加チェック不要）
$N=1$を特別分岐にしてしまう	境界条件への不安	同じ初期値・同じループで自然に$[0/1,1/1]$が生成される

次のステップ

発展: 同じ漸化式はStern-Brocot木の「分母制限付きで左から右へなぞる」特殊な経路に対応する。木そのものを構築して探索する版と比較すると理解が深まる。
次回予告: Master Levelローテーション継続（次回セッションでテーマを再選定）

自己評価

完全理解おおむね理解要復習

Day 149-Q5 — Farey数列の逐次生成（Stern-Brocot型mediant再帰・ソート/gcd不要のO(|F_N|)構成）

問題