Problem

Finden Sie den Rest, indem Sie die Anzahl der positiven Brüche von $ N! $ Durch $ 10 ^ 9 + 7 $ dividieren, wenn die ganze Zahl $ N $ angegeben wird.

Denkweise

Der Primfaktor von $ N! $ Sei {$ p_0, p_1, ..., p_k }. Außerdem sei die Zahl jedes Primfaktors { i_0, i_1, ..., i_k $}. Zu diesem Zeitpunkt wird $ N! $ Wie folgt ausgedrückt: N! = p_0^{i_0} \cdot p_1^{i_1} \cdot ... \cdot p_k^{i_k}.

Daher ist die Anzahl der Brüche von $ N! $ Is (i_0+1) \cdot (i_1+1) \cdot ... \cdot (i_k+1) Es wird.

Aus dem Obigen ist ersichtlich, dass, wenn die Zahl jedes Primfaktors von $ N! $ Berechnet wird, die Anzahl der Brüche erhalten werden kann.

Implementierung

Hier, um die Anzahl jedes Primfaktors zu zählen $ (Anzahl der in N enthaltenen Primfaktoren p!) = \ Sigma_ {k = 1} ^ {\ infty} \ left \ [\ frac {n} {p ^ k} \ right ] = \ left \ [\ frac {n} {p ^ 1} \ rechts ] + \ links \ [\ frac {n} {p ^ 2} \ rechts ] + ... $ (Details zu diesem Satz hier).

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

res = 1
p = 2  #Zu überprüfende Faktoren

# p<=sqrt(N)Es reicht aus, die Faktoren zu untersuchen, die befriedigen
while p*p <= N:
    i = 1
    # p^k(k=1~)Zählen Sie die Anzahl der Vielfachen von und addieren Sie sie
    while(N % p == 0):
        i += 1
        N //= p

    # N!Die Anzahl der Brüche von ist i_0*i_1*...*i_k
    res *= i
    p += 1

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

[PYTHON] ARC067 C - Faktoren von Factorial

Problem

Denkweise

Implementierung