综合项目：数论密室逃脱

# 综合项目：数论密室逃脱——集齐三把钥匙，打开最终密码锁

# 工具一：辗转相除法
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 工具二：质因数分解（唯一分解定理）
def factorize(n):
    parts = []
    i = 2
    m = n
    while i * i <= m:
        c = 0
        while m % i == 0:
            m = m // i
            c = c + 1
        if c > 0:
            parts.append((i, c))
        i = i + 1
    if m > 1:
        parts.append((m, 1))
    return parts

# 工具三：素数筛法
def sieve(n):
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    for i in range(2, n + 1):
        if is_p[i]:
            for j in range(i * i, n + 1, i):
                is_p[j] = False
    return [x for x in range(2, n + 1) if is_p[x]]

# 工具四：高精度加法（字符串大数）
def big_add(a, b):
    x = [int(c) for c in a[::-1]]
    y = [int(c) for c in b[::-1]]
    n = max(len(x), len(y))
    x = x + [0] * (n - len(x))
    y = y + [0] * (n - len(y))
    carry = 0
    res = []
    for i in range(n):
        s = x[i] + y[i] + carry
        res.append(s % 10)
        carry = s // 10
    if carry > 0:
        res.append(carry)
    return "".join(str(d) for d in res[::-1])

# 第一把钥匙：古老卷轴上的最大公因数
key1 = gcd(1071, 462)
print("第一把钥匙：gcd(1071, 462) =", key1)

# 第二把钥匙：360 扇门的约数个数
cnt = 1
for p, c in factorize(360):
    cnt = cnt * (c + 1)
print("第二把钥匙：360 的约数个数 =", cnt)

# 第三把钥匙：第 15 个质数
primes = sieve(60)
key3 = primes[14]
print("第三把钥匙：第 15 个质数 =", key3)

# 高精度合成最终密码
password = big_add(str(key1), str(cnt))
password = big_add(password, str(key3))
print("三把钥匙合成密码：", password)

# 密码锁 1~100：用二分查找最快试开
def unlock(target):
    left, right = 1, 100
    times = 0
    while left <= right:
        times = times + 1
        mid = (left + right) // 2
        if mid == target:
            return times
        elif mid < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print("二分试开", password, "号锁，只用了", unlock(int(password)), "次")
print("密室逃脱成功！")