3 的幂

正着乘很难枚举,倒着除反而简单:反复把 n 除以 3,只要每次都能整除(余数为 0),最终落到 1,它就是 3 的幂。

下面用两个例子走一遍:27(是) 和 45(不是)。盯住每一步的余数和除完的新值怎么变。

例一 · n = 27 起步：第一个例子 n = 27。把它放进格子里,我们要反复对它除以 3。先问:27 除以 3 余几?

27 % 3 = 0 · 能整除：27 % 3 = 0,余数是 0,说明能被 3 整除——这一关过了,执行除法。

27 ÷ 3 = 9 · 第 1 次除：除完!27 变成 9。旧值 27 变灰封存,指针移到新值 9,继续对 9 重复这套动作。

9 % 3 = 0 · 能整除：对 9 再问一遍:9 % 3 = 0,还是能整除,继续。

9 ÷ 3 = 3 · 第 2 次除：9 除以 3 得 3。指针滑到新值 3,9 封存变灰。

3 % 3 = 0 · 能整除：3 % 3 = 0,余数还是 0,最后再除一下。

3 ÷ 3 = 1 · 第 3 次除：3 除以 3 得 1!当前值落到了 1,指针停在 1 上。

当前值 = 1 · 结束：一路整除、最终落到 1,说明 27 只由 3 相乘而来,27 是 3 的幂,返回 true。整条链 27→9→3→1 就是 3³。

例二 · n = 45 起步：第二个例子 n = 45。45 看着像(能被 3 除),但藏着 3 以外的因子,我们用同一套流程把它揪出来。

45 % 3 = 0 · 能整除：45 % 3 = 0,余数 0,能整除——先别急着下结论,接着除。

45 ÷ 3 = 15 · 第 1 次除：45 除以 3 得 15。指针移到 15,继续盘问。

15 % 3 = 0 · 能整除：15 % 3 = 0,还能整除,继续除。

15 ÷ 3 = 5 · 第 2 次除：15 除以 3 得 5。指针移到 5——5 既不是 1,也明显不像 3 的倍数,关键一步来了。

5 % 3 = 2 · 余数非 0!：5 % 3 = 2,余数不是 0!这说明 45 里藏着 5 这个 3 以外的因子,除不动了。

当前值 = 5 ≠ 1 · 结束：流程停在 5,没能落到 1,说明 45 不是 3 的幂,返回 false。45 = 3² × 5,那个 5 让它出局。

补一例 · n = 81 起步：再来一例 81 = 3⁴,它要连除 4 次才到 1,正好看清楚 while 循环「除到底」是什么意思。

81 % 3 = 0 · 第 1 次除：81 % 3 = 0,除一次得 27,指针前移、81 封存。

27 % 3 = 0 · 第 2 次除：27 也整除,得 9,继续往下除。

9 % 3 = 0 · 第 3 次除：9 整除得 3,只差最后一步。

3 % 3 = 0 · 第 4 次除：第 4 次除得 1!整条链 81→27→9→3→1 每步余数全 0、干净落到 1,所以 81 是 3 的幂。是 3 的幂的数,这条链一定能走到底。

整个算法就是一个 while 循环:只要还能被 3 整除就除,循环停下后,看当前值是不是正好等于 1。

雷区实演 · n = 0 不挡会怎样：假如不写 if n < 1:n=0 时 0%3 也等于 0,除完还是 0,永远落不到 1(还可能死循环)。这就是为什么开头要先挡掉 0 和负数。

边界三连：先想最小的 1(3⁰)、零、负数三种边界,代码就稳了。

面试追问：把「循环除 3」和「1162261467 取模 O(1)」两种解法都讲清楚,是这题面试的得分点。