Найти Фактор числа

Question

Существует дающий номер N, я должен узнать число целых чисел, для которых repetitive division с N дает коэффициент.

Для Ex:

N=8 
Numbers Are 2 as: 8/2=4/2=2/2=1 
      5 as 8/5=1 
      6 as 8/6=1 
      7 and 8 

Мои Aprroach: Все числа от N/2+1 к N дает мне фактор 1 таким образом

Ans: N/2 + Check Numbers from (2, sqrt(N)) 

Временная сложность O(sqrt(N))

Есть ли лучше способы сделать t его, поскольку число может быть до 10^12 и может быть много запросов?

Может быть O(1) или O(40) (потому что 2^40 превышает 10^12)

Answer 1

Давайте посмотрим, так как число может быть до 10^12, что вы можете сделать, это создать для числа 2 to 10^6, вы можете создать и массив 40 , поэтому для каждой проверки длины, если число может быть выражено как i^(len-1)+ y, где i составляет от 2 до 10^6, а len составляет от 1 до 40.

Так время сложность O(40*Query)

Answer 2

Во-первых, ваш алгоритм не O(sqrt(N)), как вы игнорируете количество раз, вы разделите по каждому из проверяемых чисел. Если проверяемое число равно k, количество делений до получения результата (по описанному выше методу) составляет O(log(k)). Следовательно, сложность становится N/2 + (log(2) + log(3) + ... + log(sqrt(N)) = O(log(N) * sqrt(N)).

Теперь, когда у нас это есть, алгоритм может быть улучшен. Обратите внимание, что при повторном разделении вы получите 1 для зарегистрированного номера k только тогда, когда k^t <= N < 2 * k^t, где t=floor(log_k(N)).

То есть, если k^t <= N < 2 * k^(t+1). Обратите внимание на строгую < с правой стороны.

Теперь, чтобы выяснить, t, вы можете использовать метод Ньютона-Рафсона или серии Тейлора, чтобы получить логарифмы очень быстро, и указана степень сложности here. Назовем это C(N). Таким образом, сложность будет C(2) + C(3) + .... + C(sqrt(N)). Если вы можете проигнорировать стоимость вычисления log, вы можете получить это до O(sqrt(N)).

Например, в приведенном выше случае для N = 8:

• 2^3 <= 8 < 2 * 2^3: 1
• floor(log_3(8)) = 1 и 8 не удовлетворяет 3^1 <= 8 < 2 * 3^1: 0
• floor(log_4(8)) = 1 и 8 не удовлетворяет 4^1 <= 8 < 2 * 4^1: 0
• 4 Дополнительный входящий из номеров 5, 6, 7 и 8 как 8t=1 для этих чисел.

Обратите внимание, что мы не должны проверить 3 и 4, но я сделал так, чтобы проиллюстрировать этот момент. И вы можете проверить, что каждое из чисел в [N/2..N] удовлетворяет вышеуказанному неравенству и, следовательно, необходимо добавить.

Если вы используете этот подход, мы можем устранить повторяющиеся деления и получить сложность до O(sqrt(N)), если сложность вычисления логарифмов можно считать незначительной.

Answer 3

Если вы хотите получить O(1) поиск по запросу, хеш-таблица из naturals меньше или равна 10^12, которые являются полномочиями других naturals, не будут намного больше, чем 2 000 000 элементов; создать его путем итерации на основе от 1 до 1 000 000, увеличивая значение видимых ключей; корни 1,000,000...10,001 нуждаются только в квадрате; корни 10,000...1,001 нужно только кубизировать; после этого, как уже упоминалось, может быть не более 40 операций с наименьшим корнем.

Каждое значение в таблице будет представлять собой количество базовых/силовых конфигураций (например, 512 -> 2, соответствующих 2^9 и 8^3).

Answer 4

Испытательный жгут для проверки функциональности и оценки порядка сложности.

Edit при необходимости - его вики

#include <math.h> 
#include <stdio.h> 

unsigned long long nn = 0; 

unsigned repeat_div(unsigned n, unsigned d) { 
    for (;;) { 
    nn++; 
    unsigned q = n/d; 
    if (q <= 1) return q; 
    n = q; 
    } 
    return 0; 
} 

unsigned num_repeat_div2(unsigned n) { 
    unsigned count = 0; 
    for (unsigned d = 2; d <= n; d++) { 
    count += repeat_div(n, d); 
    } 
    return count; 
} 

unsigned num_repeat_div2_NM(unsigned n) { 
    unsigned count = 0; 
    if (n > 1) { 
    count += (n + 1)/2; 
    unsigned hi = (unsigned) sqrt(n); 
    for (unsigned d = 2; d <= hi; d++) { 
     count += repeat_div(n, d); 
    } 
    } 
    return count; 
} 

unsigned num_repeat_div2_test(unsigned n) { 
    // number of integers that repetitive division with n gives quotient one. 
    unsigned count = 0; 

    // increment nn per code' tightest loop 
    ... 

    return count; 
} 

/// 

unsigned (*method_rd[])(unsigned) = { num_repeat_div2, num_repeat_div2_NM, 
    num_repeat_div2_test}; 
#define RD_N (sizeof method_rd/sizeof method_rd[0]) 

unsigned test_rd(unsigned n, unsigned long long *iteration) { 
    unsigned count = 0; 
    for (unsigned i = 0; i < RD_N; i++) { 
    nn = 0; 
    unsigned this_count = method_rd[i](n); 
    iteration[i] += nn; 
    if (i > 0 && this_count != count) { 
     printf("Oops %u %u %u\n", i, count, this_count); 
     exit(-1); 
    } 
    count = this_count; 
    // printf("rd[%u](%u)  = %u. Iterations:%llu\n", i, n, cnt, nn); 
    } 

    return count; 
} 

void tests_rd(unsigned lo, unsigned hi) { 
    unsigned long long total_iterations[RD_N] = {0}; 
    unsigned long long total_count = 0; 
    for (unsigned n = lo; n <= hi; n++) { 
    total_count += test_rd(n, total_iterations); 
    } 
    for (unsigned i = 0; i < RD_N; i++) { 
    printf("Sum rd(%u,%u) --> %llu. total Iterations %llu\n", lo, hi, 
     total_count, total_iterations[i]); 
    } 
} 

int main(void) { 
    tests_rd(2, 10 * 1000); 
    return 0; 
}