結果

問題 No.2241 Reach 1
コンテスト
ユーザー lam6er
提出日時 2025-04-16 01:00:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,661 bytes
コンパイル時間 484 ms
コンパイル使用メモリ 81,896 KB
実行使用メモリ 59,936 KB
最終ジャッジ日時 2025-04-16 01:02:03
合計ジャッジ時間 2,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def divide_by_2(m):
    k = 0
    while m % 2 == 0:
        m = m // 2
        k += 1
    return m, k

def pow_mod(s, mod):
    if mod == 0:
        return 0
    result = 1
    base = 2 % mod
    while s > 0:
        if s % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        s = s // 2
    return result

def solve(N):
    max_s = 20  # sの上限を設定
    heap = []
    heapq.heappush(heap, (0, N))
    visited = {N: 0}
    
    while heap:
        steps, m = heapq.heappop(heap)
        if m == 1:
            return steps
        if steps > visited.get(m, float('inf')):
            continue
        
        # 操作1を適用
        m_new, k = divide_by_2(m)
        new_steps = steps + 1
        if m_new not in visited or new_steps < visited[m_new]:
            visited[m_new] = new_steps
            heapq.heappush(heap, (new_steps, m_new))
        
        # 操作2を適用（mが奇数の場合のみ）
        if m % 2 == 1:
            # 候補1: k=1
            new_m = m * 1 + 1
            m_div, s = divide_by_2(new_m)
            new_steps_2 = steps + 2
            if m_div not in visited or new_steps_2 < visited.get(m_div, float('inf')):
                if m_div in visited:
                    if new_steps_2 < visited[m_div]:
                        visited[m_div] = new_steps_2
                        heapq.heappush(heap, (new_steps_2, m_div))
                else:
                    visited[m_div] = new_steps_2
                    heapq.heappush(heap, (new_steps_2, m_div))
            
            # 候補2: sを1からmax_sまで試す
            for s_candidate in range(1, max_s + 1):
                mod = m
                pow_2s = pow_mod(s_candidate, mod)
                if pow_2s == 1 % mod:
                    numerator = (1 << s_candidate) - 1
                    if numerator % mod == 0:
                        k_candidate = numerator // mod
                        if k_candidate > 0:
                            new_steps_2 = steps + 2
                            if 1 not in visited or new_steps_2 < visited.get(1, float('inf')):
                                if 1 in visited:
                                    if new_steps_2 < visited[1]:
                                        visited[1] = new_steps_2
                                        heapq.heappush(heap, (new_steps_2, 1))
                                else:
                                    visited[1] = new_steps_2
                                    heapq.heappush(heap, (new_steps_2, 1))
    
    return -1  # 問題文より到達しない

N = int(input())
print(solve(N))
0