如何有效地找到 q 有限除以 b ^ k 的整数 k 的值？

Question

我们给定了两个整数 b 和 q，我们想找到一个整数 'k' 的最小值，其中 q 完全整除 b^k 或 k 不存在。我们能否有效地找出 k 的值？不仅仅是迭代 k (0, 1, 2, 3, ...) 的每个值并检查 (b^k) % q == 0) where q <= k or q >= k.

Answer 1

首先，除非q=1，否则k永远不会等于0。 k 永远不会等于 1 除非 q=b.

接下来，如果你能分解 q 和 b，那么你就可以对它们进行推理了。

如果b的质因数根本不是q的质因数，则k不存在。否则，k 必须足够大，以便 b^k 的每个因子都在 q 中表示。

这是一些伪代码：

if (q==1) return 0;
if (q==b) return 1;
// qfactors and bfactors are arrays, one element per factor
let qfactors = prime_factorization(q);
let bfactors = prime_factorization(b);
let kmin=0;
foreach (f in bfactors.unique) {
     let bcount = bfactors.count(f);
     let qcount = qfactors.count(f);
     if (qcount==0 || qcount < bcount) return -1; // k does not exist
     kmin_f = ceiling(bcount/qcount);
     if (kmin_f > kmin) let kmin = kmin_f;
}
return kmin;

Answer 2

如果q=1； k = 0

如果 b = q ; k = 1

如果 b > q 和因素 ; k = 1

如果 b < q 和因子； k != 我

如果 b != q 而不是因数； k != 我

我们知道，红利 = 除数 x 商 + 提醒

=> 股息 = 除数 x 商 [此处，提醒 = 0]

现在开始计算 Maxima 和 Minima，因为 Quotient 的值越低 'k'。

如果您将商数视为 1（最小但 spl 情况），那么 'k' 的公式变为，

k = log q/log b

Answer 3

我找到了解决办法-
如果 q 除 pow(b,k) 那么 q 的所有质因数都是 b 的质因数.现在我们可以进行迭代 q = q ÷ gcd(b,q) 而 gcd(q,b)≠1。如果q≠1迭代后，有q的质因数不是b的质因数
那么
k不存在
else
k =迭代次数.

如何有效地找到 q 有限除以 b ^ k 的整数 k 的值？

How to find the value of integer k efficiently for which q divides b ^ k finitely?

division

integer-division

greatest-common-divisor