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: Accepted

Solution code:
from collections import defaultdict
n=int(input())
sosu_list=[2]
for i in range(3, 101, 2):
    flag=0
    for j in range(2, int(i**0.5)+2):
        if i%j==0:
            flag=1
    if flag==0:
        sosu_list.append(i)
soinsu=defaultdict(int)
for i in sosu_list:
    temp=n
    while temp>=i:
        temp//=i
        soinsu[i]+=temp
kouho=soinsu.values()
cnt3=0
cnt5=0
cnt15=0
cnt25=0
cnt75=0
for a in kouho:
    if a>=2:
        cnt3+=1
    if a>=4:
        cnt5+=1
    if a>=14:
        cnt15+=1
    if a>=24:
        cnt25+=1
    if a>=74:
        cnt75+=1
ans=0
ans+=cnt75
ans+=cnt15*(cnt5-1)
ans+=cnt25*(cnt3-1)
if cnt3>=2:
    ans+=cnt5*(cnt5-1)*(cnt3-2)//2
        
print(ans)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math


mod=10**9+7
mod
ferumaC=10000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)



sosuulst={}
def soinsuu(i):
    for s in sosuulst:
        while i%s==0:
            sosuulst[s]+=1
            i//=s
    if i>1 and  not i in sosuulst :
        sosuulst.update({i:1})


N=int(input())
for i in range(2,N+1):
    soinsuu(i)


data=[sosuulst[i] for i in sosuulst]
#print(data)
count=0
for lst in [[2,4,4],[2,24],[4,14],[74]]:
    lst.reverse()
    flag=0
    temp=1
    if len(lst)<=2:
        for m,l in enumerate(lst):
            A=len([i for i in data if i>=l])-m
            if A<=0:
                flag=1
                break
            temp*=A


    else:
        A=len([i for i in data if i>=4])
        if A<=1:
            continue
        A=comb(A,2)
        temp*=A
        A=len([i for i in data if i>=2])-2
        if A<=0:
            continue
        temp*=A
    if not flag:
        #print(temp)
        count+=temp
print(count)

Submission status: Accepted

Solution code:
N=int(input())

so=[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]
log=[1]*len(so)

for num in range(1,(N)+1):
    for index,item in enumerate(so):    
        while num%item==0:
            num/=item
            log[index]+=1
        if num==1:
            break
            

ans=0
#print(sum([x>=75 for x in log]))
ans+=sum([x>=75 for x in log])
#print(ans)
ans+=sum([x>=25 for x in log])*(sum([x>=3 for x in log])-1)
ans+=sum([x>=15 for x in log])*(sum([x>=5 for x in log])-1)
ans+=sum([x>=5 for x in log])*(sum([x>=5 for x in log])-1)*(sum([x>=3 for x in log])-2)//2

#print(log)
print(ans)

Submission status: Accepted

Solution code:
from math import factorial


N = int(input())

# N! を素因数分解
fact = factorial(N)
e = [0] * (N+1)
for i in range(2, N+1):
    while fact % i == 0:
        e[i] += 1
        fact //= i


def num(m):
    return len(list(filter(lambda x: x >= m-1, e)))


ans = 0
ans += num(75)
ans += num(25) * (num(3) - 1)
ans += num(15) * (num(5) - 1)
ans += num(5) * (num(5) - 1) * (num(3) - 2) // 2

print(ans)

Submission status: Accepted

Solution code:

N = int(input())

# 1〜N をそれぞれ素因数分解して合算することで N! を素因数分解する
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)))


ans = 0
ans += num(75)
ans += num(25) * (num(3) - 1)
ans += num(15) * (num(5) - 1)
ans += num(5) * (num(5) - 1) * (num(3) - 2) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

def getPrimes(N):
    R = N + 10
    isPrime = [True] * (R + 2)
    primes = set()

    for p in range(2, R):
        if not isPrime[p]:
            continue
        primes.add(p)
        for q in range(p * 2, R, p):
            isPrime[q] = False

    return primes

primes = getPrimes(N)

def getFactors(N):
    facts = defaultdict(int)
    for p in primes:
        while N % p == 0:
            facts[p] += 1
            N //= p
    return facts

fracFacts = defaultdict(int)
for i in range(1, N + 1):
    for p, c in getFactors(i).items():
        fracFacts[p] += c

cnt = {
    2 : 0,
    4 : 0,
    14 : 0,
    24 : 0,
    74 : 0,
}

for c in fracFacts.values():
    for k in cnt.keys():
        if c >= k:
            cnt[k] += 1

ans = 0
ans += cnt[4] * (cnt[4] - 1) * (cnt[2] - 2) // 2
ans += cnt[14] * (cnt[4] - 1)
ans += cnt[24] * (cnt[2] - 1)
ans += cnt[74]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial


def factorization(n):
    arr = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0:
        arr[n] = 1

    return arr


N = int(input())

primes = Counter()

for i in range(2, N + 1):
    tp = factorization(i)
    primes += tp


V = list(primes.values())


def num(n):
    return len(list(filter(lambda x: x >= n, V)))


print(num(74) + num(24) * (num(2) - 1) + num(14) * (num(4) - 1) + num(4) * (num(4) - 1) * (num(2) - 2) // 2)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

N = int(input())

prime = [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]
p_cnt = [0]*25

for i in range(2,N+1):
    p_index = 0
    while i > 1:
        if i%prime[p_index] == 0:
            p_cnt[p_index] += 1
            i /= prime[p_index]
        else:
            p_index += 1

ans = 0

for i in range(25):
    if p_cnt[i] >= 74:
        ans += 1

for i in range(25):
    for j in range(i+1,25):
        if p_cnt[i] >= 2 and p_cnt[j] >= 24:
            ans += 1
        if p_cnt[i] >= 24 and p_cnt[j] >= 2:
            ans += 1
        if p_cnt[i] >= 4 and p_cnt[j] >= 14:
            ans += 1
        if p_cnt[i] >= 14 and p_cnt[j] >= 4:
            ans += 1

for i in range(25):
    for j in range(i+1,25):
        for k in range(j+1,25):
            if p_cnt[i] >= 2 and p_cnt[j] >= 4 and p_cnt[k] >= 4:
                ans += 1
            if p_cnt[i] >= 4 and p_cnt[j] >= 2 and p_cnt[k] >= 4:
                ans += 1
            if p_cnt[i] >= 4 and p_cnt[j] >= 4 and p_cnt[k] >= 2:
                ans += 1

print(ans)
# 74, 2*24, 4*14, 2*4*4

Submission status: Accepted

Solution code:
#756
import numpy as np
N = int(input())
 
pf = np.zeros(N+1, dtype=int)
 
def prime_fact(N):
    for i in range(2, int(N**0.5)+1):
        if N%i == 0:
            cnt = 0
            while N%i==0:
                cnt += 1
                N //= i
            pf[i] += cnt
    if N != 1:
        pf[N] += 1

for n in range(1, N+1):
    prime_fact(n)
pf = pf[np.nonzero(pf)]
 
ans = 0
x74 = np.count_nonzero(pf >= 74)
x24 = np.count_nonzero(pf >= 24)
x14 = np.count_nonzero(pf >= 14)
x4 = np.count_nonzero(pf >= 4)
x2 = np.count_nonzero(pf >= 2)
 
if x74:
    ans += x74
if x24 and x2:
    ans += x24*(x2-1)
if x14 and x4:
    ans += x14*(x4-1)
if x2 and x4>=2:
    tmp = x4*(x4-1)//2
    ans += tmp*(x2-2)

print(ans)

Submission status: Accepted

Solution code:
import bisect
import math
n = int(input())
if n == 1:
    print(0)
    exit()

def get_primenumber(N):
    #素数リスト
    prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
    for num in range(3,N+1,2):
      #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
      if all( num % prime != 0 for prime in prime_list):
        prime_list.append(num)

    return prime_list

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

sosuu = get_primenumber(100)

sosuu_list = [0] * len(sosuu)

for i in range(2, n+1):
    a = factorization(i)
    for j in a:
        index = bisect.bisect_left(sosuu, j[0])
        sosuu_list[index] += j[1]
    over_74 = len([x for x in sosuu_list if x >= 74])
    over_24 = len([x for x in sosuu_list if x >= 24])
    over_14 = len([x for x in sosuu_list if x >= 14])
    over_4  = len([x for x in sosuu_list if x >= 4])
    over_2  = len([x for x in sosuu_list if x >= 2])
    ans = over_74 + over_24 * (over_2 - 1) + over_14 * (over_4 - 1)
    if over_4 >= 2:
        ans += combinations_count(over_4, 2) * max(0, (over_2 - 2))

print(ans)

Submission status: Accepted

Solution code:
import math
def comb(a,b):
    if a < b:
        return 0
    return math.factorial(a)//(math.factorial(a-b)*math.factorial(b))
N = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
primelist = primes(N)
primes = {}
for i in primelist:
    a = sum(int(N/(i**j)) for j in range(1,8))
    primes[i] = a
cand = sorted(list(primes.values()))
ans1 = len([i for i in cand if i >= 74])
ans2 = len([i for i in cand if i >= 24])*(len([i for i in cand if i >= 2])-1)
ans3 = len([i for i in cand if i >= 14])*(len([i for i in cand if i >= 4])-1)
ans4 = comb(len([i for i in cand if i >= 4]),2)*(len([i for i in cand if i >= 2])-2)
print(ans1+ans2+ans3+ans4)

Submission status: Accepted

Solution code:
from collections import Counter

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())
a = [0] * (n + 1)
for i in range(1, n + 1):
  c = prime_factorize(i)
  for i in c:
    a[i] += 1

a3, a5, a15, a25, a75 = 0, 0, 0, 0, 0
for i in a:
  if i >= 74:
    a75 += 1 
  if i >= 24:
    a25 += 1 
  if i >= 14:
    a15 += 1 
  if i >= 4:
    a5 += 1 
  if i >= 2:
    a3 += 1 

# 重複してか終えた分を減らす。a5は同じものを丸々ダブって数えるので２で割る。
ans = a75 + a25 * (a3 - 1) + a15 * (a5 - 1) + a5 * (a5 -1) * (a3 - 2) // 2 
print(ans)

Submission status: Accepted

Solution code:
def make_divs(n):
    divisors = {}
    d = 2
    while n > 1:
        if n % d == 0:
           divisors[d] = 0
        while n % d == 0:
            divisors[d] += 1
            n //= d
        d += 1
    return divisors

n = int(input())
nn = 1
for i in range(1,n+1):
    nn *= i
if n < 10:
    print(0)
    exit()
div = make_divs(nn)
cnt = 0
t,f = 0,0
a,b = 0,0
u,s = 0,0
aa = 0
for v in div.values():
    if v >= 74:
        aa += 1
    if v >= 4:
        f += 1
    if 4 > v >= 2:
        t += 1
    if v >= 24:
        a += 1
    if 24 > v >= 2:
        b += 1
    if v >= 14:
        u += 1
    if 14 > v >= 4:
        s += 1

tmp = (f)*(f-1)*(f-2)//2 if f > 2 else 0
tmp2 = (f)*(f-1)*t//2 if f > 1 else 0
tmp3 = a*(a-1) if a > 1 else 0
tmp4 = u*(u-1) if u > 1 else 0
print(tmp + tmp2 + a*b + u*s + tmp3 + tmp4 + aa)
# print(f,t,a,b,u,s,aa)
# print(div)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def p_d():
    from collections import Counter
    N = int(input())
    li = []
    for i in range(1, N + 1):
        li.extend(prime_factorize(i))
    prime_list = Counter(li).values()

    def num(m):
        return len(list(filter(lambda x: x >= m - 1, prime_list)))

    print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1) + num(5) * (num(5) - 1) * (num(3) - 2) // 2)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

Solution code:
n = int(input())
if 9 >= n:
    print(0)
    exit()

dic = {}
dic[2] = 1
dic[3] = 1

for i in range(4,n+1):
    
    for j in dic.keys():
        
        if i % j == 0:
            while i % j == 0:
                dic[j] += 1
                i //= j
                
    if i != 1:
        dic[i] = 1


ans = {}
ans[2] = 0
ans[4] = 0
ans[14] = 0
ans[24] = 0
ans[74] = 0
for i,j in dic.items():
    for k in ans.keys():
        if j >= k:
            ans[k] +=1


count = 0
count += ans[24]*(ans[2]-1)
count += ans[74]
count += ans[14]*(ans[4]-1)
count += (ans[4]*(ans[4]-1)//2)*(ans[2]-2)
print(count)

Submission status: Accepted

Solution code:
def count(m):
    return len(list(filter(lambda x: x >= m-1, e)))


N = int(input())
# N!の素因数分解を行う
e = [0] * (N+1)  # 0~Nを何個ずつ素因数としてもつかのテーブル

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

ans = 0
ans += count(75)
ans += count(25) * (count(3) - 1)
ans += count(15) * (count(5) - 1)
ans += (count(5) * (count(5)-1) * (count(3) - 2)) // 2
print(ans)

Submission status: Accepted

Solution code:
def num(m):  # eの要素のうちm-1以上のものの個数
    return len(list((filter(lambda x: x >= m-1, e))))


N = int(input())
e = [0] * (N+1)  # その素因数がいくつあるか
for i in range(2, N+1):
    cur = i  # iを素因数分解する
    for j in range(2, i+1):
        while cur % j == 0:  # jを素因数にもつなら
            e[j] += 1  # カウントを増やす
            cur //= j
# これで素因数分解が完了


print(num(75) + num(25)*(num(3)-1) + num(15)*(num(5)-1) + num(5)*(num(5)-1)*(num(3) - 2) // 2)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def integer_factorization_perm(N):
    prime_count = collections.Counter()
    for n in range(1, N+1):
        for i in range(2, int(math.sqrt(n)) + 2):
            while n % i == 0:
                n //= i
                prime_count[i] += 1
        if n > 1:
            prime_count[n] += 1
    return prime_count

def main():
    N = I()
    primes = integer_factorization_perm(N)
    over74, over24, over14, over4, over2 = 0, 0, 0, 0, 0
    for k, v in primes.items():
        if v >= 74:
            over74 += 1
        if v >= 24:
            over24 += 1
        if v >= 14:
            over14 += 1
        if v >= 4:
            over4 += 1
        if v >= 2:
            over2 += 1
    cnt = 0
    '''
    print('74: ', over74)
    print('24: ', over24)
    print('14: ', over14)
    print('4: ', over4)
    print('2: ', over2)
    '''

    cnt += over74
    if over2 > 1:
        cnt += over24 * (over2 - 1)
    if over4 > 1:
        cnt += over14 * (over4 - 1)
    if over2 > 1 and over4 > 0:
        cnt += (over2 - 2) * over4 * (over4 - 1) // 2
    print(cnt)

main()

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import defaultdict
from itertools import combinations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    divisor=defaultdict(int)
    for i in range(1,N+1):
        x=2
        while i!=1:
            if i%x==0:
                divisor[x]+=1
                i//=x
            else:
                x+=1
    divisor_2=[]
    divisor_4=[]
    divisor_14=[]
    divisor_24=[]
    divisor_74=[]
    for k,v in divisor.items():
        if v>=2:
            divisor_2.append(k)
        if v>=4:
            divisor_4.append(k)
        if v>=14:
            divisor_14.append(k)
        if v>=24:
            divisor_24.append(k)
        if v>=74:
            divisor_74.append(k)
    ans=0
    for a in divisor_2:
        for p in combinations(divisor_4,2):
            if not a in p:
                ans+=1
    for a in divisor_14:
        for b in divisor_4:
            if a!=b:
                ans+=1
    for a in divisor_24:
        for b in divisor_2:
            if a!=b:
                ans+=1
    ans+=len(divisor_74)
    print(ans)
                

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = {}
for i in range(1, N+1):
  a = i
  dig = 1
  p = 2
  while a != 1:
    j = 0
    while a % p == 0:
      j += 1
      a //= p
      dig *= p
    if j != 0:
      if p in D:
        D[p] += j
      else:
        D[p] = j
    p += 1
    if p > int(i**(1/2)) and dig != i:
      if i//dig in D:
        D[i//dig] += 1
      else:
        D[i//dig] = 1
      break
A = [D[i] for i in D]
A.sort()
L = len(A)
i2, i4, i14, i24, i74 = 0, 0, 0, 0, 0
p2, p4, p14, p24, p74 = 0, 0, 0, 0, 0
j = 0
while j < L:
  if A[j] >= 2 and p2 == 0:
    i2 = j
    p2 = 1
  if A[j] >= 4 and p4 == 0:
    i4 = j
    p4 = 1
  if A[j] >= 14 and p14 == 0:
    i14 = j
    p14 = 1
  if A[j] >= 24 and p24 == 0:
    i24 = j
    p24 = 1
  if A[j] >= 74 and p74 == 0:
    i74 = j
    p74 = 1
  j += 1
S = (L - i74) * p74
S += (L - i2 - 1) * (L - i24) * p2 * p24
S += (L - i4 - 1) * (L - i14) * p4 * p14
S += ((L - i2 - 2) * (L - i4) * (L - i4 - 1) * p2 * p4) // 2
print(S)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from math import floor, sqrt
from functools import reduce
from operator import mul

def prime_factorize_factorial(n):
    res = defaultdict(int)
    for i in range(n, 0, -1):
        while i % 2 == 0:
            res[2] += 1
            i //= 2
        if i == 1:
            continue
        for j in range(3, floor(sqrt(n))+1, 2):
            while i % j == 0:
                res[j] += 1
                i //= j
            if i == 1:
                break
        else:
            res[i] += 1
    return res

def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    upper = reduce(mul, range(n, n-r, -1), 1)
    lower = reduce(mul, range(r, 0, -1), 1)
    return upper // lower

n = int(sys.stdin.readline().rstrip())

def main():
    pcnt = prime_factorize_factorial(n)
    cnt_pcnt_atleast = [0] * 75
    for c in pcnt.values():
        if c <= 74:
            cnt_pcnt_atleast[c] += 1
        else:
            cnt_pcnt_atleast[74] += 1
    
    for i in range(74, 0, -1):
        cnt_pcnt_atleast[i-1] += cnt_pcnt_atleast[i]
    
    res = 0
    
    # 75
    res += cnt_pcnt_atleast[74]
    # 25 * 3
    res += cnt_pcnt_atleast[24] * (cnt_pcnt_atleast[2] - 1)
    # 15 * 5
    res += cnt_pcnt_atleast[14] * (cnt_pcnt_atleast[4] - 1)
    # 5 * 5 * 3
    res += comb(cnt_pcnt_atleast[4], 2) * (cnt_pcnt_atleast[2] - 2)

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import collections
import copy
N=int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

table=collections.defaultdict(int)
for i in range(1,N+1):
  tmp=factorization(i)
  for a,b in tmp:
    table[a]+=b

divisors=[[5,5,3],[15,5],[25,3],[75]]
ans=0
for x in divisors:
  tmp=[set() for i in range(len(x))]
  for i,y in enumerate(x):
    for z in table:
      if table[z]>=y-1:
        tmp[i].add(z)
    if len(tmp[i])==0:
      break
  for y in tmp[0]:
    if len(x)>1:
      for z in tmp[1]:
        if y==z:
          continue
        if len(x)>2:
          if y>z:
            continue
          for w in tmp[2]:
            if z==w or w==y:
              continue
            else:
              ans+=1
        else:
              ans+=1
    else:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def f(x):
    global e
    return len(list(filter(lambda y:y>=x-1,e)))

def main():
    n = inp()
    global e
    e = [0 for _ in range(n+1)]
    for i in range(2,n+1):
        x = i
        for j in range(2,i+1):
            while x % j == 0:
                e[j] += 1
                x //= j
    print( f(75) + f(25)*(f(3)-1) + f(15)*(f(5)-1) + f(5)*(f(5)-1)*(f(3)-2)//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = {}
for n in range(2, N+1):
    K = n
    for k in range(2, n):
        if k not in D:
            continue
        while K % k == 0:
            K //= k
            D[k] += 1
        if K == 1:
            break
    else:
        D[n] = 1
a2 = sum(v >= 2 for v in D.values())
a4 = sum(v >= 4 for v in D.values())
a14 = sum(v >= 14 for v in D.values())
a24 = sum(v >= 24 for v in D.values())
a74 = sum(v >= 74 for v in D.values())
ans = 0
if a2 > 2:
    ans += (a2-2)*a4*(a4-1)//2
if a2 > 1:
    ans += (a2-1)*a24
if a4 > 1:
    ans += (a4-1)*a14
if a74:
    ans += a74
print(ans)

Submission status: Accepted

Solution code:
prime_sieve=[1 for i in range(51)]
prime_sieve[0]=0
prime_sieve[1]=0
prime=[]

for i in range(2,51):
  if prime_sieve[i]==1:
    prime.append(i)
    for j in range(2,50//i+1):
      prime_sieve[i*j]=0


#print(len(prime))
count=[0 for i in range(15)]

X=int(input())

for i in range(2,X+1):
  for j in range(15):
    while i%prime[j]==0:
      i=i//prime[j]
      count[j]+=1


tw=0
fr=0
# 5 5 3

fif=0

# 5 15

tf=0


# 25 3 


sf=0



for i in range(15):
  if count[i]>=4:
    fr+=1
  if count[i]>=2:
    tw+=1
  if count[i]>=14:
    fif+=1
  if count[i]>=24:
    tf+=1
  if count[i]>=74:
    sf+=1




ans=fr*(fr-1)*(tw-2)//2+fif*(fr-1)+tf*(tw-1)+sf
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


nn=int(input())

if nn==1:
  print(0)
  exit(0)

dct=defaultdict(int)
for i in range(2,nn+1):
  for k,m in factorization(i):
    dct[k]+=m

li=[0]*1000

for k,v in dct.items():
  li[v]+=1

a74=sum(li[74:])
a24=sum(li[24:])
a14=sum(li[14:])
a4=sum(li[4:])
a2=sum(li[2:])

print(a74+(a24*(a2-1)+a14*(a4-1))+(max(a4*(a4-1)//2,0))*max(a2-2,0))

Submission status: Accepted

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 sum([ei>=m-1 for ei in 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: Accepted

Solution code:
import sys
from collections import defaultdict
N = int(input())
d = defaultdict(int)
for n in range(1, N+1):
    m = 2
    while n != 1:
        if n % m == 0:
            d[m] += 1
            n //= m
            m = 2
        else:
            m += 1
ans = 0
# count 3, 5, 15, 25, 75
count = [0, 0, 0, 0, 0]
for v in d.values():
    if v >= 74:
        count[4] += 1
    elif v >= 24:
        count[3] += 1
    elif v >= 14:
        count[2] += 1
    elif v >= 4:
        count[1] += 1
    elif v >= 2:
        count[0] += 1
ans += count[4]
ans += sum(count[3:])*(sum(count)-1)
ans += sum(count[2:])*(sum(count[1:])-1)
ans += sum(count[1:])*(sum(count[1:])-1)//2*(sum(count)-2)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


N = int(sys.stdin.buffer.readline())

counts = [0] * 101
for n in range(1, N + 1):
    for f in get_factors(n):
        counts[f] += 1

t = []
for c in counts:
    if c >= 2:
        t.append(c)
counts = t

# 素因数の使い方のパターン数が
# 3, 25 と 3, 5, 5 と 15, 5 と 75 のとき約数が75個
ans = 0
for i, j, k in itertools.combinations(range(len(counts)), r=3):
    if counts[i] >= 2 and counts[j] >= 4 and counts[k] >= 4:
        ans += 1
    if counts[i] >= 4 and counts[j] >= 2 and counts[k] >= 4:
        ans += 1
    if counts[i] >= 4 and counts[j] >= 4 and counts[k] >= 2:
        ans += 1
for i, j in itertools.combinations(range(len(counts)), r=2):
    if counts[i] >= 2 and counts[j] >= 24:
        ans += 1
    if counts[i] >= 24 and counts[j] >= 2:
        ans += 1
    if counts[i] >= 4 and counts[j] >= 14:
        ans += 1
    if counts[i] >= 14 and counts[j] >= 4:
        ans += 1
for c in counts:
    if c >= 74:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# e[i]: N!の素因数分解でのiの指数
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

# eの要素で(M-1)以上のものの個数
def num(M:int):
    return len(tuple(filter(lambda x: x >= M-1, e)))

answer = num(75)
# -1は、num(25)の分
answer += num(25) * (num(3) - 1)
answer += num(15) * (num(5) - 1)
# //2は、二つのnum(5)は区別しないから
answer += num(5) * (num(5) - 1) * (num(3) - 2) // 2

print(answer)

Submission status: Accepted

Solution code:
PList = [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]
PNum  = len(PList)
Beki  = [0]*(PNum)

N = int(input())
for n in range(1,N+1):
    nn = n
    for i in range(PNum):
        while nn % PList[i] == 0:
            Beki[i]+=1
            nn //= PList[i]
'''
75 = (74+1)
   = (24+1)(2+1)
   = (14+1)(4+1)
   = (4+1)(4+1)(2+1)
'''

beki02 = 0
beki04 = 0
beki14 = 0
beki24 = 0
beki74 = 0

for i in Beki:
    if i >= 2:
        beki02+=1
    if i >= 4:
        beki04+=1
    if i >= 14:
        beki14+=1
    if i >= 24:
        beki24+=1
    if i >= 74:
        beki74+=1

ans = 0
ans += beki74
ans += beki24*(beki02-1)
ans += beki14*(beki04-1)
ans += beki04*(beki04-1)//2*(beki02-2)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

pn=[2];A=100
for L in range(3,A):
  chk=True
  for L2 in pn:
    if L%L2 == 0:chk=False
  if chk==True:pn.append(L)

mul = [0 for i in range(101)]
for i in range(1,N+1):
  for j in pn:
    if j > i:
      break
    temp = i
    while True:
      if temp%j == 0:
        temp /= j
        mul[j] += 1
        continue
      else:
        break
        
prime_num = []
for index, num in enumerate(mul):
  if num != 0:
    prime_num.append([index,num])

ans = 0
# 4,4,2の取り出し
from itertools import combinations
nums442 = list(combinations(prime_num,3))
for num in nums442:
  if num[0][1]>=2 and num[1][1]>=4 and num[2][1]>=4:
    ans += 1
  if num[0][1]>=4 and num[1][1]>=2 and num[2][1]>=4:
    ans += 1
  if num[0][1]>=4 and num[1][1]>=4 and num[2][1]>=2:
    ans += 1

# 14,4の取り出し
nums14_4 = list(combinations(prime_num,2))
for num in nums14_4:
  if num[0][1]>=14 and num[1][1]>=4:
    ans += 1
  if num[0][1]>=4 and num[1][1]>=14:
    ans += 1

# 24,2の取り出し
nums24_2 = list(combinations(prime_num,2))
for num in nums24_2:
  if num[0][1]>=24 and num[1][1]>=2:
    ans += 1
  if num[0][1]>=2 and num[1][1]>=24:
    ans += 1
    
# 74の取り出し
for num in prime_num:
  if num[1] >= 74:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import collections

n=int(input())
a=[1]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

for i in range(1,n+1):
    a+=prime_factorize(i)


a=collections.Counter(a)
a=a.most_common()



v=0
w=0
count=0

for i in range(len(a)):
    if a[i][1]+1>=5:
        v+=1
    elif 3<=a[i][1]+1<=4:
        w+=1

if v<2 or v-2+w<1:
    print(0)
    exit()

for i in range(len(a)):

    if a[i][1]+1>=75:
        count+=1+v+w-1+v-1
    elif a[i][1]+1>=25:
        count+=v+w-1+v-1
    elif a[i][1]+1>=15:
        count+=v-1
    else:
        continue

print((v*(v-1)//2)*(w+v-2)+count)

Submission status: Accepted

Solution code:
n=int(input())
c=[0]*(n+1)
for i in range(2,n+1):
	j=2
	while j*j<=i:
		while i%j==0:
			c[j]+=1
			i//=j
		j+=1
	if i>1:
		c[i]+=1
f=lambda x:sum(y+1>=x for y in c)
print(f(75)+f(25)*(f(3)-1)+f(15)*(f(5)-1)+f(5)*(f(5)-1)//2*(f(3)-2))