Number of divisors of factorial

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

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

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

The-Legend
10 лет назад
14

Комментарии (13)

Показать архивные | Написать комментарий?

The-Legend

10 лет назад, скрыть # |

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

→ Ответить

The-Legend

10 лет назад, скрыть # |

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

→ Ответить

sgtlaugh

10 лет назад, скрыть # |

← 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).

→ Ответить

The-Legend

10 лет назад, скрыть # ^ |

← Rev. 6 →

-14

→ Ответить

Na2a

10 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

The-Legend

10 лет назад, скрыть # ^ |

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.

→ Ответить

VastoLorde95

10 лет назад, скрыть # ^ |

← Rev. 3 →

You only need to check primes upto $\text{[math]}$ since the power of all primes greater than $\text{[math]}$ in n! will be 1. And you can precalculate how many primes are in the range $\text{[math]}$

→ Ответить

Monster_Nerd

5 лет назад, скрыть # ^ |

-34

Yeah got it. How to solve for higher n?

→ Ответить

OddImage

10 лет назад, скрыть # |

← Rev. 6 →

-33

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

→ Ответить

The-Legend

10 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

nickitat

10 лет назад, скрыть # |

← 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 $\text{[math]}$ it`s clear. For any prime $\text{[math]}$ (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 $\text{[math]}$ values.

Amount of big primes with fixed p(d) (= amount of primes with exactly p(d) multiples) equals $\text{[math]}$ . Any of them gives p(d) + 1 to the answer thus in the result we need to assign ans = ans * (p(d) + 1)^C.