Problem:


Score : 400 points

Problem Statement

You are given an integer N. Among the divisors of N! (= 1 \times 2 \times ... \times N), how many Shichi-Go numbers (literally "Seven-Five numbers") are there?

Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.

Note

When a positive integer A divides a positive integer B, A is said to a divisor of B.
For example, 6 has four divisors: 1, 2, 3 and 6.

Constraints

1 \leq N \leq 100

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of the Shichi-Go numbers that are divisors of N!.

Sample Input 1

9

Sample Output 1

0

There are no Shichi-Go numbers among the divisors of 9! = 1 \times 2 \times ... \times 9 = 362880.

Sample Input 2

10

Sample Output 2

1

There is one Shichi-Go number among the divisors of 10! = 3628800: 32400.

Sample Input 3

100

Sample Output 3

543



Sample input:
9


Sample output:
0

Submission status: Runtime Error

Solution code:
from itertools import combinations
N = int(input())
def get_sieve_of_eratosthenes(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return prime
prime = get_sieve_of_eratosthenes(N)
n = len(prime)
ans = 0
divNum = [0] + [ N//i for i in range(1,N+1) ]
for p in prime:
    ip = p * p
    while ip <= N:
        divNum[p] += divNum[ip]
        ip *= p

for i in range(n):
    if 74 <= divNum[prime[i]]:
        ans += 1
    for j in range(n):
        if i != j and 4 <= divNum[prime[i]] and 14 <= divNum[prime[j]]:
            ans += 1
        if i != j and 2 <= divNum[prime[i]] and 24 <= divNum[prime[j]]:
            ans += 1
        for k in range(j+1,n):
            if i != j and i != k:
                if 2 <= divNum[prime[i]] and 4 <= divNum[prime[j]] and 4 <= divNum[prime[k]]:
                    ans += 1
            
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
typedef long long ll;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans[ohara],a,b,c,d,cmp,cmpp,m,h,w,x,y,sum,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

void cal(ll dat){
    rrep(i,2,n+1){
        if(dat<=1)break;
        if(dat%i!=0)continue;
        while(1){
        dat/=i;
        ans[i]++;
        if(dat%i!=0||dat<=1)break;
        }
    }
    return;
}

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);

    rep(i,ohara)ans[i]=1;
    cin>>n;
    rrep(i,2,n+1){
        cal(i);
    }
    rep(i,n+1){
        rep(j,n+1){
            rep(k,n+1){
                if(i==j||j==k||i==k)continue;
                if(ans[i]>=5&&ans[j]>=5&&ans[k]>=3)cnt++;
            }
        }
    }
    Cout(cnt);
    cnt/=2;
    rep(i,n+1){
        rep(j,n+1){
            if(i==j)continue;
            if(ans[i]>=3&&ans[j]>=25)cnt++;
            if(ans[i]>=5&&ans[j]>=15)cnt++;
        }
    }
    rep(i,n+1){
        if(ans[i]>=75)cnt++;
    }
    Cout(cnt);
    return 0;
}

Submission status: Runtime Error

Solution code:
ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
N = int(input())
l = [0 for _ in range(98)]
def fac(n):
  for k in ps:
   if n == 1:
     break
   if n % k == 0:
    l[k] += 1
    fac(n // k)
    break

for i in range(2,N+1):
  fac(i)

p = [k for k in l if k > 1]

ans = 0

def num(n):
  r = 0
  for k in p:
    if k >= n:
      r += 1
  return(r)

if p[0] >= 74:
  ans += 1

#5*15

ans += (num(14) * (num(14) - 1))
ans += (num(14) * (num(4) - num(14)))

#3 * 25
ans += (num(24) * (num(24) - 1))
ans += (num(24) * (num(2) - num(24)))

#3 * 5 * 5
ans += (num(4) * (num(4) - 1) * (num(4) - 2) // 2)
ans += (num(4) * (num(4) - 1) //2) * (num(2) - num(4))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
import math
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)
n=int(input())
L=[]
for j in range(2,n+1):
    I=j
    s=0
    R=int(I)
    while s==0:
        for i in range(2,R+1):
            if I%i==0:
                I=I/i
                if I==1:
                    s=1
                L.append(i)
                break
c=Counter(L)
c=[0 for i in range(100)]
for i,j in c.most_common():
  c[j]+=1
 
s=0
s+=sum(c[4:])*(sum(c[4:])-1)*sum(c[2:]-2)//2
s+=sum(c[14:])*(sum(c[4:])-1)
s+=sum(c[24:])*(sum(c[2:])-1)
s+=sum(c[74:])
print(s)

Submission status: Runtime Error

Solution code:
import numpy as np
N = input()
E = np.ones(N + 1)
for i in range(2,N + 1):
  if E[i] != 0:
    for j in range(i * 2,N,i):
      E[j] = 0

n = []
for i in range(1,N + 1):
  if E[i] != 0:
    n.append(i)

print(len(list(combinations(n,2))))

Submission status: Runtime Error

Solution code:
n=int(input())
f=[]
w=[0,0,0,0,0]
for i in range(2,n+1):
    c=0
    r=int(i**0.5)
    for j in range(2,r+2):
        while i%j==0:
            c+=1
            i=i//j
        if c!=0:
            f.append([j,c])
            c=0
    if i!=1:
        f.append([i,1])
f.sort()
d=[]
ans=0
cou=f[0][1]
for i in range(1,len(f)):
    if f[i][0]==f[i-1][0]:
        cou+=f[i][1]
    else:
        d.append(cou)
        cou=1
d.append(cou)

for i in d:
    for j,num in enumerate([2,4,14,24,74]):
        if i>=num:
            w[j]+=1
print(w[4]+w[3]*(w[0]-1)+w[2]*(w[1]-1)+w[1]*(w[1]-1)*(w[0]-2)//2)

Submission status: Runtime Error

Solution code:
n=int(input())
f=[]
w=[0,0,0,0,0]
for i in range(2,n+1):
    c=0
    r=int(i**0.5)
    for j in range(2,r+2):
        while i%j==0:
            c+=1
            i=i//j
        if c!=0:
            f.append([j,c])
            c=0
    if i!=1:
        f.append([i,1])
f.sort()
d=[]
ans=0
cou=f[0][1]
for i in range(1,len(f)):
    if f[i][0]==f[i-1][0]:
        cou+=f[i][1]
    else:
        d.append(cou)
        cou=1
d.append(cou)

for i in d:
    for j,num in enumerate([2,4,14,24,74]):
        if i>=num:
            w[j]+=1
print(w)
print(w[4]+w[3]*(w[0]-1)+w[2]*(w[1]-1)+w[1]*(w[1]-1)*(w[0]-2)//2)

Submission status: Runtime Error

Solution code:
from collections import Counter as c

def fact(n):
    d=[]
    for i in range(2,int(n**0.5)+2):
        while n%i==0:
            n//=i
            d.append(i)
    if n!=1:d.append(n)
    return c(d)

n=int(input())
d=c()
for i in range(1,n+1):
    d+=fact(i)

f=lambda n,x:sum(1 for i in p(d.values(),n) if all(map(lambda x,y:x>=y,i,x)))
print(f(3,(2,4,4))//2+f(2,(2,24))+f(2,(4,14))+f(1,(74,)))

Submission status: Runtime Error

Solution code:
from scipy.special import perm, comb

a = int(input())

b = [0 for i in range(15)]
j = 0
c = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
d = [0 for i in range(101)]
p = 0
pp = 0
co = 0
for i in range(1,101):
  k = i
  while True:
    if k % c[j] == 0 and k >= c[j]:
      b[j] += 1
      k //= c[j]
    else:
      j += 1
      if j == 15:
        j = 0
        break
  for k in range(15):
    if b[k] >= 4:
      p += 1
    elif b[k] >= 2:
      pp += 1
  if i >= 10:
    d[i] = comb(p, 2,exact=True)*comb(pp, 1,exact=True) + comb(p, 3,exact=True)
  p = 0
  pp = 0
print(d[a])

Submission status: Runtime Error

Solution code:
N = int(input()) e=[0]*(N+1)
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
cur //= j
def num(m):
    return len(list(filter(lambda x: x >= m-1, e)))
print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1)
    + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Runtime Error

Solution code:
n=int(input())
f=[]
for i in range(2,n+1):
    c=0
    r=int(i**0.5)
    for j in range(2,r+2):
        while i%j==0:
            c+=1
            i=i//j
        if c!=0:
            f.append([j,c])
            c=0
    if i!=1:
        f.append([i,1])
f.sort()
d=[]
ans=0
cou=f[0][1]
for i in range(1,len(f)):
    if f[i][0]==f[i-1][0]:
        cou+=f[i][1]
    else:
        d.append(cou)
        cou=1
d.append(cou)

a74=0
for i in d:
    if i>=74:
        a74+=1
ans+=a74


a2=0
a24=0
for i in d:
    if i>=24:
        a24+=1
    if i>=2 and i<24:
        a2+=1
ans+=a2*a24
if a24>=2:
    ans+=a24*(a24-1)//2

    
a2,a4=0,0
for i in d:
    if i>=4:
        a4+=1
    elif i>=2:
        a2+=1
if a4>=2 and a2>=1:
    ans+=a4*(a4-1)//2*a2
if a4>=3:
    ans+=a4*(a4-1)*(a4-2)//2

    
a4,a14=0,0
for i in d:
    if i>=14:
        a14+=1
    if i>=4 and i<14:
        a4+=1
ans+=a4*a14
if a14>=2:
    ans+=a14*(a14-1)//2

print(ans)

Submission status: Runtime Error

Solution code:
import math
import sympy
n=int(input())
a=math.factorial(n)
#print(a)
#a=32400

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
ps=prime_factors(a)
sy={}
for i in ps:
    if i not in sy:
        sy[i]=1
    else:
        sy[i]+=1
#aaaaaaaaaaa
#sy=sympy.factorint(a)
count75=0
count25=0
count15=0
count5=0
count3=0
for k in sy.values():
    #print(k)
    if k+1>=75:
        count75+=1
    if k+1>=25:
        count25+=1
    if k+1>=15:
        count15+=1
    if k+1>=5:
        count5+=1
    if k+1>=3:
        count3+=1

#print(count75)
#print(count25*(count3-1))
#print(count15*(count5-1))
#print((count5*(count5-1)*(count3-2))/2)
print(int(count75+count25*(count3-1)+count15*(count5-1)+(count5*(count5-1)*(count3-2))/2))

Submission status: Runtime Error

Solution code:
import math
import sympy
n=int(input())
a=math.factorial(n)
#print(a)
#a=32400
sy=sympy.factorint(a)
count75=0
count25=0
count15=0
count5=0
count3=0
for k in sy.values():
    #print(k)
    if k+1>=75:
        count75+=1
    if k+1>=25:
        count25+=1
    if k+1>=15:
        count15+=1
    if k+1>=5:
        count5+=1
    if k+1>=3:
        count3+=1

#print(count75)
#print(count25*(count3-1))
#print(count15*(count5-1))
#print((count5*(count5-1)*(count3-2))/2)
print(int(count75+count25*(count3-1)+count15*(count5-1)+(count5*(count5-1)*(count3-2))/2))

Submission status: Runtime Error

Solution code:
import math

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

def usage(n):
    tmp=0
    fct = factorize(n)
    for div in divisorize(fct):
        t = 1
        for i in div:
          t*=(i[1]+1)
        if t==75:
          tmp+=1
    print(tmp)

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
  
def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]
  
usage(F)

Submission status: Runtime Error

Solution code:
import sympy
import math

x = int(input())
X = math.factorial(x)
count = 0
for _ in range(X):
    a = sympy.divisor_count(100000)
    if a == 75:
        count = count + 1

print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heapreplace
from itertools import count, product, combinations
from functools import partial, reduce
from math import floor, ceil, sqrt, gcd
from collections import defaultdict, deque

def Primes_fnct():
    def b_search(L,t):
        #増大列LについてL[:+1]の要素すべてがt以下であるような最大のi<len(L)を返す。
        search_range = [-1, len(L)]
        update_range = lambda mid: search_range.__setitem__(t<L[mid], mid)
        for _ in [0]*search_range[1].bit_length():
            update_range(sum(search_range)//2)
        return search_range[0]
    
    P = [2,]
    Pappend = P.append
    Q = deque([])
    Qappend = Q.append
    Qpopleft = Q.popleft
    hq = [] 
    integer = count(3,2)
    current_i = 1
    valid_range = 1
    def Primes(*, max_int=None):
        nonlocal valid_range, current_i
        if max_int is None:
            return P[:]

        if  max_int - current_i <= 1:
            return P[:b_search(P,max_int)+1]

        for i in integer:
            if i >= valid_range:
                if Q:
                    q = Qpopleft()
                    heappush(hq, (q**2,q))
                valid_range = Q[0]**2 if Q else i**2

            m,r = hq[0] if hq else (0,0)
            if i != m:
                Pappend(i)
                Qappend(i)

            while m == i:
                heapreplace(hq, (m+2*r, r))
                m,r = hq[0]

            current_i = i
            if max_int - current_i <=1:
                break 
        return P[:]
    return Primes

def factorization(m, Primes=None):
    F = defaultdict(int)
    if m < 2:
        return F

    while not m&1:
        F[2] += 1
        m >>= 1

    if Primes is None:
        Primes = Primes_fnct()

    Primes = deque(Primes(max_int=ceil(sqrt(m))+1))
    Primespopleft = Primes.popleft

    while m > 1 and Primes:
        p = Primespopleft()
        while not m%p:
            m //= p
            F[p] += 1

    if m > 1:
        F[m] += 1
    return F

def solve():
    N = int(input())
    Primes = Primes_fnct()
    F = defaultdict(int)
    for i in range(1,N+1):
        f = factorization(i)
        for k in f.keys():
            F[k] += f[k]
    P = defaultdict(set)
    for k in F.keys():
        for n in (2,4,14,24,74):
            if F[k] >= n:
                P[n] = P[n]|{k,}
    res = 0
    for Q in (((2,1),(4,2)), ((2,1),(24,1)), ((4,1),(14,1)), ((74,1),)):
        R = set()
        if all(len(P[q[0]]) >= q[1] for q in Q):
            for r in product(*(combinations(P[q[0]],q[1]) for q in Q)):
                r_ = [i for j in r for i in j]
                if len(r_) == len(set(r_)):
                    R |= {r,}
        res += len(R)

    return res



if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heapreplace
from itertools import count, product, combinations
from functools import partial, reduce
from math import floor, ceil, sqrt, gcd
from collections import defaultdict, deque

def Primes_fnct():
    def b_search(L,t):
        #増大列LについてL[:+1]の要素すべてがt以下であるような最大のi<len(L)を返す。
        search_range = [-1, len(L)]
        update_range = lambda mid: search_range.__setitem__(t<L[mid], mid)
        for _ in [0]*search_range[1].bit_length():
            update_range(sum(search_range)//2)
        return search_range[0]
    
    P = [2,]
    Pappend = P.append
    Q = deque([])
    Qappend = Q.append
    Qpopleft = Q.popleft
    hq = [] 
    integer = count(3,2)
    current_i = 1
    valid_range = 1
    def Primes(*, max_int=None):
        nonlocal valid_range, current_i
        if max_int is None:
            return P[:]

        if  max_int - current_i <= 1:
            return P[:b_search(P,max_int)+1]

        for i in integer:
            if i >= valid_range:
                if Q:
                    q = Qpopleft()
                    heappush(hq, (q**2,q))
                valid_range = Q[0]**2 if Q else i**2

            m,r = hq[0] if hq else (0,0)
            if i != m:
                Pappend(i)
                Qappend(i)

            while m == i:
                heapreplace(hq, (m+2*r, r))
                m,r = hq[0]

            current_i = i
            if max_int - current_i <=1:
                break 
        return P[:]
    return Primes

def factorization(m, Primes=None):
    F = defaultdict(int)
    if m < 2:
        return F

    while not m&1:
        F[2] += 1
        m >>= 1

    if Primes is None:
        Primes = Primes_fnct()

    Primes = deque(Primes(max_int=ceil(sqrt(m))+1))
    Primespopleft = Primes.popleft

    while m > 1 and Primes:
        p = Primespopleft()
        while not m%p:
            m //= p
            F[p] += 1

    if m > 1:
        F[m] += 1
    return F

def solve():
    N = int(input())
    Primes = Primes_fnct()
    F = defaultdict(int)
    for i in range(1,N+1):
        f = factorization(i)
        for k in f.keys():
            F[k] += f[k]
    P = defaultdict(set)
    for k in F.keys():
        for n in (2,4,14,24,74):
            if F[k] >= n:
                P[n] = P[n]|{k,}
    res = 0
    for Q in (((2,1),(4,2)), ((2,1),(24,1)), ((4,1),(14,1)), ((74,1),)):
        R = set()
        for r in product(*(combinations(P[q[0]],q[1]) for q in Q)):
            r_ = [i for j in r for i in j]
            if len(r_) == len(set(r_)):
                R |= {r,}
        res += len(R)

    return res



if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
import math
import sympy

N = math.factorial(int(input()))
nums = sympy.divisors(N)

hit = 0
for x in nums:
    if len(sympy.divisors(x)) == 75:
        hit += 1

print(hit)