ОК, это забавно.
Определите f (i) = (p ^ i - 1) / (p - 1)
Напишите k в довольно забавной "базе"«где значение позиции i - это f (i).
Вы делаете это от старшей к младшей значащей цифры.Итак, сначала найдите наибольшее j такое, что f (j) <= k.Затем вычислим частное и остаток от k / f (j).Сохраните частное как q_j, а остаток как r.Теперь вычислим частное и остаток от r / f (j-1).Сохраните частное как q_ {j-1}, а остаток снова как r.Теперь вычислим частное и остаток от r / f (j-2).И так далее. </p>
Это генерирует последовательность q_j, q_ {j-1}, q_ {j-2}, ..., q_1.(Обратите внимание, что последовательность заканчивается в 1, а не в 0.) Затем вычислите q_j * p ^ j + q_ {j-1} * p ^ (j-1) + ... q_1 * p.Это ваш N.
Пример: k = 9, p = 3. Так что f (i) = (3 ^ i - 1) / 2. f (1) = 1, f (2) = 4,f (3) = 13. Таким образом, наибольшее j с f (j) <= 9 равно i = 2 с f (2) = 4. Возьмите частное и остаток от 9 / 4. Это частное от 2 (которое являетсяцифра вместо нашего 2) и остаток от 1. </p>
Для этого остатка от 1 найдите частное и остаток от 1 / f (1).Коэффициент равен 1, остаток равен нулю, так что мы закончили.
Итак, q_2 = 2, q_1 = 1. 2 * 3 ^ 2 + 1 * 3 ^ 1 = 21, что является правильным N.
У меня есть объяснение на бумаге, почему это работает, но я не уверен, как передать это в тексте ... Обратите внимание, что f (i) отвечает на вопрос: «Сколько факторов p есть в (p^ я)!».Как только вы найдете наибольшее значение i, j, такое, что j * f (i) меньше k, и поймете, что вы действительно находите самое большое j * p ^ i меньше N, остальные виды выпадают из стирки.,В нашем примере с p = 3, например, мы получаем 4 p, полученные от продукта 1-9, еще 4 от продукта 10-18 и еще один от 21. Эти первые два просто кратны p ^2;f (2) = 4 говорит нам о том, что каждое кратное p ^ 2 добавляет к продукту еще 4 p.
[update]
Код всегда помогает уточнить.Сохраните следующий скрипт Perl как foo.pl и запустите его как foo.pl <p> <k>.Обратите внимание, что ** является оператором возведения в степень в Perl, bdiv вычисляет частное и остаток для BigInts (целые числа с неограниченной точностью), а use bigint указывает Perl использовать BigInts везде.
#!/usr/bin/env perl
use warnings;
use strict;
use bigint;
@ARGV == 2
or die "Usage: $0 <p> <k>\n";
my ($p, $k) = map { Math::BigInt->new($_) } @ARGV;
sub f {
my $i = shift;
return ($p ** $i - 1) / ($p - 1);
}
my $j = 0;
while (f($j) <= $k) {
$j++;
}
$j--;
my $N = 0;
my $r = $k;
while ($r > 0) {
my $val = f($j);
my ($q, $new_r) = $r->bdiv($val);
$N += $q * ($p ** $j);
$r = $new_r;
$j--;
}
print "Result: $N\n";
exit 0;