結果

問題 No.1880 Many Ways
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:25:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,683 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 66,884 KB
最終ジャッジ日時 2025-06-12 16:25:59
合計ジャッジ時間 12,763 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def find_largest_divisor(n, max_limit):
    if n == 1:
        return 1
    for d in range(min(n, max_limit), 0, -1):
        if n % d == 0:
            return d
    return 1

def factorize_a(A):
    if A == 0:
        return []
    factors = []
    while A > 1:
        d = find_largest_divisor(A, 126)
        if d == 1:
            factors.append(1)
            break
        factors.append(d)
        A = A // d
    return factors

def main():
    A = int(sys.stdin.readline())
    if A == 0:
        print("1 0")
        return
    factors = factorize_a(A)
    sum_factors = sum(factors)
    if sum_factors == 0:
        print("1 0")
        return
    if sum_factors > 126:
        print("1 0")
        return
    N = 1 + sum_factors + 1
    edges = []
    current_node = 1
    # Connect node 1 to layer 1
    layer_size = factors[0]
    for i in range(layer_size):
        node = current_node + i + 1
        edges.append((1, node))
    current_node += layer_size
    # Connect layers between each other
    for i in range(len(factors) - 1):
        s = factors[i]
        t = factors[i+1]
        start_u = current_node - s + 1
        end_u = current_node
        end_v = current_node + t
        for u in range(start_u, end_u + 1):
            for v in range(current_node + 1, end_v + 1):
                edges.append((u, v))
        current_node += t
    # Connect last layer to N
    s = factors[-1]
    start_u = current_node - s + 1
    end_u = current_node
    for u in range(start_u, end_u + 1):
        edges.append((u, N))
    print(f"{N} {len(edges)}")
    for edge in edges:
        print(f"{edge[0]} {edge[1]}")

if __name__ == "__main__":
    main()
0