algorithm - 求一个数的商

Question

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

例如:

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

我的方法:从 N/2+1 到 N 的所有数字都给我商 1 所以

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

时间复杂度O(sqrt(N))

有没有更好的方法来做到这一点，因为数字可以达到 10^12 并且可以有很多查询？

可以是O(1)还是O(40)(因为2^40超过了10^12)

Answer 1

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

根据需要编辑 - 它的 wiki

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