Как эффективно найти значение целого числа k, для которого q делит b ^ 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 = 0

Если b = q;k = 1

Если b> q и множители;k = 1

Если b Если b! = q, а не множители;k! = I

Мы знаем, Дивиденд = Делитель x Коэффициент + Напоминание

=> Дивиденд = Делитель x Коэффициент [Здесь, Напоминание = 0]

Теперь перейдем к расчетуМаксимумы и минимумы, как ниже значение фактора, тем ниже значение «к».

Если вы рассматриваете фактор как 1 (наименьший, но случай разрыва), тогда ваша формула для «к» становится,

k = log q / log b

Answer 2

Я нашел решение -
Если q делит pow (b, k) , то все простые множители q являются простыми множителями b .Теперь мы можем делать итерации q = q ÷ gcd (b, q) , тогда как gcd (q, b) ≠ 1 .Если q ≠ 1 после итераций, существуют простые множители q , которые не являются простыми множителями b
, то
k нене существует
иначе
k = нет итерации .

Answer 3

Прежде всего, k никогда не будет равно нулю, если q = 1.k никогда не будет равно единице, если 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;