賞品を隠せて参加者が見つけられない部屋の数を求めるPythonプログラム

問題の概要

あるゲーム番組では、2n個の部屋が円形に配置されています。そのうちの1つの部屋には賞品が隠されており、参加者はそれを見つけ出すことが課題となります。部屋には時計回りの順に 1, 2, 3, …, n, -n, -(n−1), …, -1 という番号が付けられています。

各部屋にはドアがあり、そこから別の部屋へ移動できます。すべてのドアには印「x」が付けられていて、現在の部屋から距離 x 離れた位置にある部屋へ通じていることを意味します。x が正の値なら時計回りに x 番目の部屋へ、負の値なら反時計回りに |x| 番目の部屋へ開きます。

私たちが求めたいのは、賞品が隠されていた場合に参加者が決して訪問できない、つまり見つけるのが困難になる部屋の数です。

入力例とその動作

たとえば input_array = [[4, 2]] という入力が与えられたとき、出力は [2] になります。

入力の各要素は2つの値を持ちます。1つ目の値 n は部屋の総数の半分、2つ目の値は参加者が探索を始める部屋の番号です。この例では 2×4 = 8 個の部屋があり、参加者は2番目の部屋から探索を開始します。部屋は時計回りに 1, 2, 3, 4, -4, -3, -2, -1 の順に並んでいます。

参加者が部屋を訪れる順序は次のようになります。

2 → -4 → -1 → 1 → 3 → -2 → -1 → 1 → 3 → -2 → …

このサイクルには部屋 4 と部屋 -3 が一切現れません。したがって、賞品がこの2つの部屋のいずれかに隠されていれば、参加者は二度とそれを見つけられません。よって答えは 2 となります。

解法のアプローチ

この問題の鍵となるのは、「2の冪乗の剰余(mod r)がいつ初めて 1 に戻るか」、すなわち2の乗法位数(multiplicative order)を求めることです。オイラーの定理により 2^φ(r) ≡ 1 (mod r) が成り立つため、まずオイラー関数の値を計算し、その素因数を順に割り去りながら条件を満たす最小の指数を特定します。

具体的な手順は以下のとおりです。

1. prime_num_find(n):エラトステネスの篩の要領で n 未満の素数リストを生成します。奇数のみを走査することで効率化しています。
   • p_nums := 値 2 で初期化した新しいリスト
   • check := バイト列(bytearray)によるフラグ管理用リスト
   • 3 から n まで 2 ずつ増加させながら、check が未処理の値を素数として登録し、その倍数にフラグを立てる
2. factor_finder(p):45000 未満の素数リストを利用して p を素因数分解します。結果は「素因数 → 指数」の辞書形式で返します。平方根を超えた時点で試し割りを打ち切り、残った p が 1 より大きければそれ自身を素因数として追加します。
3. euler_func(p):素因数分解の結果をもとに、オイラー関数 φ(p) = Π (q−1)·q^(e−1) を計算します。
4. solve(input_array):各クエリに対して次を処理します。
   • r = 2p + 1 を計算し、gcd(r, q mod r) で約分する
   • r に対するオイラー関数の値 t_value を求める
   • t_value の各素因数 value について、「t_value が value で割り切れ、かつ 2^(t_value/value) mod r == 1」を満たす限り t_value を割り続ける
   • 最終的な t_value は 2 の mod r における乗法位数となり、答えは 2p − t_value

実装コード(Python)

それでは、上記の手順を実際に実装してみましょう。

import math

def prime_num_find(n):
    p_nums = [2]
    check = bytearray(n)
    for value in range(3, n, 2):
        if check[value]:
            continue
        p_nums.append(value)
        for i in range(3 * value, n, 2 * value):
            check[i] = 1
    return p_nums

def factor_finder(p):
    p_nums = prime_num_find(45000)
    f_nums = {}
    for value in p_nums:
        if value * value > p:
            break
        while p % value == 0:
            p //= value
            f_nums[value] = f_nums.get(value, 0) + 1
    if p > 1:
        f_nums[p] = 1
    return f_nums

def euler_func(p):
    f_nums = factor_finder(p)
    t_value = 1
    for value in f_nums:
        t_value *= (value - 1) * value ** (f_nums[value] - 1)
    return t_value

def solve(input_array):
    output = []
    for item in input_array:
        p, q = item[0], item[1]
        r = 2 * p + 1
        r //= math.gcd(r, q % r)
        t_value = euler_func(r)
        for value in factor_finder(t_value):
            while t_value % value == 0 and pow(2, t_value // value, r) == 1:
                t_value //= value
        output.append(2 * p - t_value)
    return output

print(solve([[4, 2]]))

入力

[[4, 2]]

出力

[2]

処理のポイント

• pow(2, e, r) の活用:Python の組み込み関数 pow は第3引数に剰余を指定でき、巨大な冪乗も高速かつ省メモリで計算できます。
• 前計算による高速化:素数表を 45000 未満で一度だけ生成すれば、√(2×10⁹) 程度までの値の素因数分解に再利用でき、複数クエリにも耐えられる構成になります。
• 位数の削減:φ(r) の素因数を順に除いていくことで、無駄な探索なしに 2 の乗法位数を効率的に特定できます。

まとめ

本記事では、円形に並ぶ部屋の中で「賞品を隠しても参加者が発見できない部屋」の数を求める Python プログラムを紹介しました。素数の生成、素因数分解、オイラー関数、そして冪乗の剰余計算を組み合わせることで、一見すると複雑な探索問題を数学的にエレガントかつ高速に解くことができます。競技プログラミングにおける位数計算のテクニックとしても応用範囲が広いので、ぜひ理解を深めてみてください。