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

Question

我们给出了两个整数b和q，并且我们想要找到整数'k'的最小值，其中q完全除以b ^ k或k不存在。我们能有效地找出k的价值吗？不仅迭代k（0,1,2,3，...）的每个值并且检查（b ^ k）％q == 0）其中q <= k或q> = k。

Answer 1

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

接下来，如果你可以分解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！=我

我们知道，Dividend = Divisor x Quotient + Remainder

=> Dividend = Divisor x Quotient [Here，Reminder = 0]

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

如果您将商数视为1（最低但是分裂情况）那么'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不存在 其他 k =迭代次数。