[PYTHON] ARC067 C - Facteurs factoriels

problème

Trouvez le reste en divisant le nombre de fractions positives de $ N! $ Par $ 10 ^ 9 + 7 $ lorsque l'entier $ N $ est donné.

Façon de penser

Soit le facteur premier de $ N! $ {$ P_0, p_1, ..., p_k }. Aussi, laissez le nombre de chaque facteur premier être { i_0, i_1, ..., i_k $}. A ce moment, $ N! $ Est exprimé comme suit: N! = p_0^{i_0} \cdot p_1^{i_1} \cdot ... \cdot p_k^{i_k}.

Par conséquent, le nombre de fractions de $ N! $ Est (i_0+1) \cdot (i_1+1) \cdot ... \cdot (i_k+1) Il devient.

D'après ce qui précède, on peut voir que si le nombre de chaque facteur premier de $ N! $ Est calculé, le nombre de fractions peut être obtenu.

la mise en oeuvre

Ici, pour compter le nombre de chaque facteur premier $ (Nombre de facteurs premiers p contenus dans N!) = \ Sigma_ {k = 1} ^ {\ infty} \ left \ [\ frac {n} {p ^ k} \ right ] = \ left \ [\ frac {n} {p ^ 1} \ droite ] + \ gauche \ [\ frac {n} {p ^ 2} \ droite ] + ... $ (Détails de ce théorème ici).

import math
N = math.factorial(int(input()))

res = 1
p = 2  #Facteurs à vérifier

# p<=sqrt(N)Il suffit d'enquêter sur les facteurs qui satisfont
while p*p <= N:
    i = 1
    # p^k(k=1~)Comptez le nombre de multiples de et additionnez-les ensemble
    while(N % p == 0):
        i += 1
        N //= p

    # N!Le nombre de fractions de est i_0*i_1*...*i_k
    res *= i
    p += 1

if(N != 1):
    res *= 2
print(res % (10**9+7))