Алгоритмы теории чисел. Большинство делителей в сегменте

Question

Алгоритмы теории чисел. Большинство делителей в сегменте

Я ищу эффективный алгоритм для решения следующей проблемы. Позволять d(n) обозначает число положительных делителей n где n положительное целое число Нам дают немного 1 <= a <= b <= 10^18 и задача состоит в том, чтобы найти максимальное значение d на сегменте [a..b] и (может быть, нам понадобится более сложный алгоритм для этой части), чтобы найти число, которое максимизирует значение d,

Некоторое время назад я нашел следующий код в свободном доступе: http://ideone.com/qvxPj

unsigned long long n, res;
int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};

unsigned long long mul(unsigned long long a, unsigned long long b){
unsigned long long res = 0;

while (b){
if (b & 1LL) res = (res + a);
if (res >= n) return 0;
a = (a << 1LL);
b >>= 1LL;
}

return res;
}

void backtrack(int i, int lim, unsigned long long val, unsigned long long r){
if (r > res) res = r;
if (i == p) return;

int d;
unsigned long long x = val;

for (d = 1; d <= lim; d++){
x = mul(x, primes[i]);
if (x == 0) return;
backtrack(i + 1, d, x, r * (d + 1));
}
}

int main(){
p = sizeof(primes) / sizeof(int);

while (scanf("%llu", &n) != EOF){
res = 0;
backtrack(0, 100, 1, 1);
printf("Maximum number of divisors of any number less than %llu = %llu\n", n, res);
}
return 0;
}

Я буду очень рад, если кто-нибудь объяснит мне, как это работает, потому что (как по мне) эта программа работает очень быстро.

Заранее благодарю за любую помощь.

5

algorithm c++number-theory numbers

Решение

Другие решения

В качестве дополнения к ответу @stgatilov, я буду обосновывать выбор, чтобы ограничивать простые числа меньшими простыми числами, меньшими или равными 71.

Я использовал слегка модифицированную версию кода, чтобы отметить наибольшее число, имеющее максимальное число делителей. За 1000000000000000000 или 999999999999999999 я получил:

897612484786617600 = 2⁸ * 3⁴ * 5² * 7² * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37

с 103680 делителями.

Это означает, что для всего числа из 18 десятичных цифр не учитывается простое число, большее 37, находится целое число с наибольшим числом делителей.

1

Источник

Accepted Answer

Он перебирает все числа следующим образом:

num = P1^D1 * P2^D2 * P3^D3 * ... * Ps^Ds
constraints:
Pi <= 71
1 <= Di <= 100
sequence (Pi) is a sorted list of first s primes
sequence (Di) is nonincreasing
num <= n

Давайте проверим первое ограничение. Предположим, что минимальное оптимальное число имеет простой множитель q> 71. Если какой-то премьер п <= 71 не используется в этом номере, то мы можем заменить Q с п в той же силе. Очевидно, что число делителей останется прежним, но число уменьшится -> противоречие. Тогда не существует неиспользуемого простого числа меньше 71. Но произведение всех простых чисел до 71 уже настолько велико, что рассматриваемое нами число должно быть больше 64-разрядного. N. Это невозможно.

Теперь давайте объясним второе и третье ограничения. Предположим, что наше минимальное оптимальное число имеет простое число Q в его факторизации, но не имеет некоторого простого п, где п < Q. Тогда мы можем заменить Q с п в том же порядке число будет иметь такое же количество делителей, но станет меньше -> противоречие. Это означает, что все простые числа в факторизации искомого (минимального) числа должны быть точно первыми s простые числа. В наборе простых чисел не может быть дыр.
КСТАТИ, ди <= 100 очевидно, потому что даже 2 ^ 100 уже не соответствует 64-битному целому числу.

Теперь мы должны объяснить четвертое ограничение. Предположим, что D [I] < D [+ 1] для некоторых я. Тогда мы можем заменить P [i] ^ D [i] * P [i + 1] ^ D [i + 1] с P [i] ^ D [i + 1] * P [i + 1] ^ D [i], и число станет меньше. Например, замените 5 ^ 2 * 7 ^ 3 на 5 ^ 3 * 7 ^ 2: число делителей такое же, но результат меньше. Очевидно, что если мы ищем минимальное оптимальное число, мы можем смело принять это условие.

Теперь давайте рассмотрим код.
mul это небольшая функция, которая рассчитывает произведение а также б. Он рассчитывается по смешной двоичной процедуре. Основная причина этой процедуры: если продукт больше, чем N, затем функция возвращает 0. Эта процедура является лишь защитой от переполнения, которое может произойти в противном случае.

Наконец мы добрались до backtrack, Это обычный рекурсивный поиск. val текущий номер, r это число делителей, i показывает индекс простого числа, которое мы собираемся добавить сейчас, lim ограничивает мощность каждого простого числа до 100. В самом начале вы видите обновление текущего оптимального ответа (хранится в res) и жесткое условие остановки (все простые числа использованы).

Затем есть цикл, который проверяет каждую степень на текущее простое число. Он начинается с степени 1, поскольку нулевые степени запрещены. Поддерживает текущий номер в x и умножает это на число Пи каждая итерация для увеличения мощности. Если x становится больше чем N, это немедленно останавливается. Наконец, он вызывает себя для поиска следующего простого числа.

3