Блог пользователя The-Legend

Number of divisors of factorial

Автор The-Legend, история, 8 лет назад, По-английски

Hello!

What is the fastest way to calc the number of divisors of n! , s.t 1 <= n <= 1e8.

Number of test cases <= 5000 .

I've stucked at this point while solving this problem EasyFact

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by The-Legend (previous revision, new revision, compare).

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by The-Legend (previous revision, new revision, compare).

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

What's wrong with prime factorization? Since the number of test cases <= 5000, you should pre-calculate the prime factorization of all numbers <= 10^8. Now use this to answer each test case in sqrt(n) * log(n).

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 6   Проголосовать: нравится -14 Проголосовать: не нравится

    .

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Prime divisors of N! (N factorial) are less or equal to N. So, for each prime P ( <= N), you can calculate its power in factorization of N! using this code:

      int calc(int n, int p) { // finds maximum alpha such that n mod p^alpha = 0
  int alpha = 0;
  while (n) {
    n /= p;
    alpha += n;
  }
  return alpha;
}
      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        There are 5 millions primes up to 1e8, for each one of them I need to calling " calc " , and this is for one test case , it's too slow.

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          You only need to check primes upto since the power of all primes greater than in n! will be 1. And you can precalculate how many primes are in the range

          → Ответить
»
8 лет назад, # |
← Rev. 6   Проголосовать: нравится -33 Проголосовать: не нравится

UPD:I've misunderstood the problem.Ignore this comment,thanks.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    You are wrong.

    I want N! not N

    Try this case

    T = 1;

    N = 5;

    then N! = 120 = 2^3 * 3 * 5 then the number of divisors equal to 16

    Your answer is 2

    → Ответить
»
8 лет назад, # |
← Rev. 7   Проголосовать: нравится +29 Проголосовать: не нравится

We need to find for all primes in range [1, N] powers in which that numbers occurs in the N!'s factorization. For primes from it`s clear. For any prime (lets call that set "big primes") we can observe, that d's power in factorizations of numbers from [1, N] is only 0 or 1. Thus d's power in the answer equal to amount of numbers in [1, N] which d devides. Lets call that power p(d). Then we can observe that all numbers with same value of p(·) is a consecutive segment of "big primes" and moreover p(·) has only values.

Amount of big primes with fixed p(d) (= amount of primes with exactly p(d) multiples) equals . Any of them gives p(d) + 1 to the answer thus in the result we need to assign ans = ans * (p(d) + 1)C.

I`m sure that my explanation was really ugly and I hope code will be useful.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Maybe can help.

→ Ответить