結果

問題 No.2929 Miracle Branch
ユーザー hirayuu_yc
提出日時 2025-02-07 12:20:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 4,010 bytes
コンパイル時間 609 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 109,496 KB
最終ジャッジ日時 2025-02-07 12:20:31
合計ジャッジ時間 12,011 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys,math,random
    sys.setrecursionlimit(10000)
    data = sys.stdin.read().split()
    if not data:
        return
    X = int(data[0])
    
    # 特殊情况：X == 1
    if X == 1:
        # 只有一个茶色顶点挂1个緑色顶点，总顶点数2
        out_lines = []
        out_lines.append("2")
        out_lines.append("1 2")
        out_lines.append("b g")
        sys.stdout.write("\n".join(out_lines))
        return

    # Miller–Rabin 素性测试（适用于64位整数）
    def is_prime(n):
        if n < 2:
            return False
        # 试除一些小质数
        small_primes = [2,3,5,7,11,13,17,19,23,29]
        for p in small_primes:
            if n == p:
                return True
            if n % p == 0:
                return False
        d = n - 1
        s = 0
        while d % 2 == 0:
            s += 1
            d //= 2
        # 对于64位整数，一组足够的测试基
        for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
            if a % n == 0:
                continue
            x = pow(a, d, n)
            if x == 1 or x == n-1:
                continue
            for _ in range(s-1):
                x = pow(x, 2, n)
                if x == n-1:
                    break
            else:
                return False
        return True

    # Pollard–Rho 算法
    def pollard_rho(n):
        if n % 2 == 0:
            return 2
        x = random.randrange(2, n)
        y = x
        c = random.randrange(1, n)
        d = 1
        while d == 1:
            x = (x*x + c) % n
            y = (y*y + c) % n
            y = (y*y + c) % n
            d = math.gcd(abs(x-y), n)
            if d == n:
                return pollard_rho(n)
        return d

    # 递归因式分解
    def factorize(n):
        if n == 1:
            return []
        if is_prime(n):
            return [n]
        d = pollard_rho(n)
        return factorize(d) + factorize(n//d)
    
    # 对 X 进行质因数分解
    fac_list = factorize(X)
    from collections import Counter
    cnt = Counter(fac_list)
    factors = []   # 此处我们构造“因子列表” F
    # 对于质因数2，成对组合
    if 2 in cnt:
        c = cnt[2]
        del cnt[2]
        pairs = c // 2
        for _ in range(pairs):
            factors.append(4)
        if c % 2 == 1:
            factors.append(2)
    # 对于其他质因数，直接每个都单独作为一个因子
    for p, e in cnt.items():
        for _ in range(e):
            factors.append(p)
    # 为了输出结果确定，我们可以将因子排序（顺序不影响总和）
    factors.sort()
    k = len(factors)
    total_green = sum(factors)  # 挂在茶色顶点上的緑色顶点数之和
    n = k + total_green         # 总顶点数 = 茶色顶点数 + 緑色顶点数
    if n > 200000:
        sys.stdout.write("-1")
        return
    
    # 下面构造树：
    # 我们令编号 1,…,k 为茶色顶点，它们构成一条链（1–2, 2–3, …）
    edges = []
    for i in range(1, k):
        edges.append((i, i+1))
    # 对于每个茶色顶点 i (编号 1..k)，挂上 factors[i-1] 个緑色叶子，编号依次从 k+1 开始
    current = k + 1
    for i in range(k):
        a = factors[i]
        for _ in range(a):
            edges.append((i+1, current))
            current += 1
    # 构造各顶点颜色：1..k 为茶色 "b" ，其余为緑色 "g"
    colors = []
    for i in range(1, k+1):
        colors.append('b')
    for i in range(k+1, n+1):
        colors.append('g')
    
    # 输出时严格按照格式要求：
    # 第一行：顶点数 n
    # 接下来 n-1 行：边 (u v)
    # 最后一行：n 个字符（用空格分隔）表示各顶点颜色
    out_lines = []
    out_lines.append(str(n))
    for u, v in edges:
        out_lines.append(f"{u} {v}")
    out_lines.append(" ".join(colors))
    sys.stdout.write("\n".join(out_lines))
    
if __name__ == '__main__':
    solve()
0