日月双塔（灯塔问题）

日月双塔

题目描述

有两座灯塔，高度分别为 a 和 b。每次操作可以将任意一座灯塔的高度乘以任意素数。求最少需要多少次操作才能使两座灯塔高度相等。

解题思路

核心观察

1. 目标状态：让 a 和 b 都变成它们的最小公倍数 lcm(a,b)，此时两塔高度相等。

2. 最大公约数的作用：

   • 设 g = gcd(a, b) 为最大公约数
   • 则 lcm(a, b) = a × b / g

3. 需要的操作次数：

   • a 需要乘以 lcm/a = b/g
   • b 需要乘以 lcm/b = a/g

4. 素因子个数的含义：

   • 每次操作只能乘以一个素数
   • 把 x 变成 y 需要的次数 = x 的素因子个数（带重数）
   • 例如：12 = 2² × 3¹，需要 2 + 1 = 3 次操作

算法步骤

1. 计算 g = gcd(a, b)
2. 计算 a’ = a / g, b’ = b / g
3. 计算 a’ 的素因子个数 + b’ 的素因子个数

代码实现

a, b = map(int, input().split())

import math
g = math.gcd(a, b)

def count(n):
    cnt = 0
    d = 2
    while d * d <= n:
        while n % d == 0:
            cnt += 1
            n //= d
        d += 1
    if n > 1:
        cnt += 1
    return cnt

ans = count(b // g) + count(a // g)

print(ans)

代码解析

count 函数

• 从 d = 2 开始试除
• 如果 n 能被 d 整除，则 d 是素因子，计数器 +1，并除去该因子
• d 遍历到 √n 即可（如果还有剩余 >1 的数，也是素因子）

时间复杂度

• 求最大公约数：O(log min(a, b))
• 分解质因数：O(√n)
• 总计：O(√max(a, b))