如何高效求解使q整除b^k的最小整数k（或判断k不存在）

当然可以高效解决这个问题！完全不用傻乎乎地逐个试k的值，我们靠数学推导就能快速找到答案，或者直接判断不存在这样的k。下面给你拆解清楚：

首先得明确一个关键前提：q能整除b^k的必要条件是，q的所有质因数都必须是b的质因数。

• 如果q存在某个质因数是b没有的，那无论k取多大，b^k的质因数都只会来自b，永远覆盖不了这个额外的质因数，这种情况直接判定「k不存在」。
• 特殊情况：如果q=1，那不管b是什么，k=0就行（因为任何数的0次方是1，1能被1整除）。

当q的所有质因数都在b的质因数集合里时，我们通过质因数的指数来计算最小k：

1. 对b和q分别做质因数分解：
   • 比如b = p₁^e₁ * p₂^e₂ * ... * pₙ^eₙ（p是质因数，e是对应指数）
   • q = p₁^f₁ * p₂^f₂ * ... * pₙ^fₙ（只保留和b共有的质因数，其他的已经被排除了）
2. 对每个共同质因数pᵢ，计算满足 k*eᵢ ≥ fᵢ 的最小整数kᵢ，也就是向上取整(fᵢ / eᵢ)
3. 最终的最小k就是所有kᵢ中的最大值——因为这个k要同时满足所有质因数的指数要求，必须取最大的那个才能覆盖所有情况。

如果不想做复杂的质因数分解，也可以用辗转相除法的思路逐步剥离q中的因子：

• 先计算g = gcd(b, q)：
  • 如果g=1：要么q=1（k=0），要么k不存在
  • 如果g≠1：反复计算q中每个质因数的指数，比如对g中的质因数p，计算它在q中的总次数f，在b中的总次数e，然后算出对应的kᵢ=ceil(f/e)，更新q为q除以p^f，直到q变成1，最后取所有kᵢ的最大值。

• 例子1：b=12，q=108
  • b的质因数：2²、3¹；q的质因数：2²、3³
  • 对2：ceil(2/2)=1；对3：ceil(3/1)=3
  • 最小k=3，验证：12³=1728，1728÷108=16，确实整除；k=2时12²=144，144÷108=1.333…不整除，所以3是最小解。
• 例子2：b=6，q=20
  • q的质因数包含5，但b的质因数只有2和3，没有5，所以k不存在。
• 例子3：b=0，q=5
  • 0^1=0能被5整除，k=0时0⁰无意义，所以最小k=1。

• 当b=0时：
  • q=1 → k=0
  • q>1 → k=1（0^1=0能被任何正整数整除）
  • q=0 → 问题无意义（除数不能为0）
• 当q=0时：问题本身不成立，不符合整除的定义。

内容的提问来源于stack exchange，提问作者goodKarma