寻找一个数字的商

Question

有一个给定数字N，我必须找出其中N为repetitive division给整数的商数。

对于防爆：

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))。

现在我们已经明白了，算法可能会得到改进。观察到，通过重复划分，只有当k^t <= N < 2 * k^t其中t=floor(log_k(N))时，您才会得到1的检查号码k。

也就是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)，小于或等于10^12的自然数的哈希表是其他自然数的幂不会大于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

测试工具用于验证功能并评估复杂性的顺序。

根据需要编辑 - 其维基

#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; 
}