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
import math

def c():
    sosus = "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"
    sosus  = sosus.split("、")
    sosus = list(map(int,sosus))
    dic = dict(zip(sosus,len(sosus) * [0]))
    N =int(input())
    p = 0
    for i in range(2,N+1):
        lim = int(math.sqrt(i)) + 1
        cot = 0
        p = 0
        while   i != 1:
            p = sosus[cot]
            if i % p == 0:
                dic[p] += 1
                i = i // p
            else:
                cot += 1
        if i != 1:
            sosus[i] += 1
    ans = 0

    pats = [[14,4],[24,2]]
    for v in dic.values():
        if v >= 74:
            ans += 1

    for pat in pats:
        temp = 0
        temp2 = 0
        p1,p2 = pat
        for v in dic.values():
            if v>= p1:
                temp += 1
        for v in dic.values():
            if v>= p2:
                temp2 += 1
        ans += max(temp * (temp2 - 1),0)

    temp = 0
    temp2 = 0
    p1,p2 = 4,2
    for v in dic.values():
        if v>= p1:
            temp += 1
    for v in dic.values():
        if v>= p2:
            temp2 += 1
    ans += max(temp * (temp-1) //2 *  (temp2 - 2),0)
    print(ans)
if __name__ == "__main__":
    c()

Submission status: Accepted

Solution code:
N = int(input())

def isPrime(x):
    if x==2: return True
    if x%2==0: return False
    i=3
    while i>0 and i*i<=x:
        if x%i==0: i=-100
        i+=2
    return i>0

P = [p for p in range(2,100) if isPrime(p)]
nP = len(P)

f = [0]*nP

for n in range(1,N+1):
    for ip, p in enumerate(P):
        k = n
        while k%p==0:
            f[ip] += 1
            k//=p

r=0
x = [0]*nP
for i in range(nP):
    x[i]=(x[i]+1)*3-1
    for j in range(nP):
        x[j]=(x[j]+1)*5-1
        for k in range(j,nP):
            x[k]=(x[k]+1)*5-1
            ok=True
            for l in range(nP):
                if x[l] > f[l]:
                    ok = False
                    break
            if ok: r+=1
            x[k]=(x[k]+1)//5-1
        x[j]=(x[j]+1)//5-1
    x[i]=0

print(r)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

# Summarize count of factor within list
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res

# nCr
def nCr(n,r):
  if n<r:
    return 0
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

# 方針
# 素因数が74個同じ数をもつ数字は七五数になる
# 素因数が24個同じ数をもち、2個同じ数を持つ数字も七五数になる
# …
# 素因数が4個同じ数をもち、4個同じ数を持ち、2個同じ数を持つ数字も七五数になる
# n!を素因数分解して上記を何パターン作れるか考える

# 手順
# n!を素因数分解する
# 74個もち・24個もち・14個持ち・4個持ち・2個もちに分類
# 上記で挙げたパターンを全て数え上げて足す

# 注意
# 例えば、24個持ち・2個持ちを取る場合
# 24個持ちから取った数字は2個持ちと重複できないので引いておくこと
# また、2個持ちなどは引数が2個のものからだけでなく
# それ以上の個数を持つものからも取れる
# つまり、24個持ちも14個持ち・4個持ち・2個持ちとして扱える

# n=1 のときはバグるので return 0 するようにした
# 最大・最小パターンはチェックする癖をつけたい

def main():
  n=I()

  if n==1:
    return 0

  l1=[]
  for i in range(2,n+1):
    l1+=getPrimeList(i)

  l1=summarize_list(l1)

  l1=sorted(l1,key=lambda x:x[1],reverse=True)

  # print(l1)

  # print(l)

  ans=[]

  # 75・25・15・5・3
  l2=[0]*5
  for x in l1:
    if x[1]>=74:
      l2[0]+=1
    elif x[1]>=24:
      l2[1]+=1
    elif x[1]>=14:
      l2[2]+=1
    elif x[1]>=4:
      l2[3]+=1
    elif x[1]>=2:
      l2[4]+=1

  # print(l2)

  # 75
  ans.append(l2[0])

  # 25・3
  ans.append(sum(l2[:2])*(sum(l2[:5])-1))

  # 15・5
  ans.append(sum(l2[:3])*(sum(l2[:4])-1))

  # 5・5・3
  ans.append(nCr(sum(l2[:4]),2)*(sum(l2[:5])-2))

  return sum(ans)

# main()
print(main())

Submission status: Accepted

Solution code:
N=int(input())

def factoring(M,n=2):
    for i in range(n,int(M**0.5)+1):
        if M%i==0:
            ret = factoring(M//i,i)
            ret[i] = ret.get(i,0)+1
            return ret
    return {M:1}

p = {2:0}
for i in range(2,N+1):
    for k,v in factoring(i).items():
        p[k] = p.get(k,0)+v

c = [0]*4
for n in p.values():
    if n>=24:c[3]+=1
    elif n>=14:c[2]+=1
    elif n>=4:c[1]+=1
    elif n>=2:c[0]+=1

ans = 0
ans += p[2]>=74
ans += c[3]*(sum(c)-1)
c[2] += c[3]
ans += c[2]*(c[1]+c[2]-1)
c[1] +=c[2]
ans += c[0]*c[1]*(c[1]-1)//2
ans += c[1]*(c[1]-1)*(c[1]-2)//2
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())


def factorint(N):

    table = []
    while(N > 1):
        for i in range(2,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    table.append(i)
                break
    return table

l = []
for n in range(1,N+1):
    l += factorint(n)
c = collections.Counter(l)
com = {74:0,24:0,14:0,4:0,2:0}
# print(c)
for key in c.keys():
    if c[key] >= 74:
        com[74] += 1
    if c[key] >= 24:
        com[24] += 1
    if c[key] >= 14:
        com[14] += 1
    if c[key] >= 4:
        com[4] += 1
    if c[key] >= 2:
        com[2] += 1
# print(com)
ans = 0
ans += com[74]
ans += com[24] * (com[2] - 1)
ans += com[14] * (com[4] - 1)
ans += com[4] * (com[4] - 1)* (com[2] - 2) //2
print(ans)

Submission status: Accepted

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]
np=25
cnts={p:0 for p in ps}
N=int(input())
for n in range(2,N+1):
    for p in reversed(ps):
        while n%p==0:
            cnts[p]+=1
            n//=p

nums={3:0,5:0,15:0,25:0,75:0}
for p, cnt in cnts.items():
    for n in nums:
        if cnt+1 >= n:
            nums[n]+=1
ans=0
if nums[5] >= 2:
    ans += (nums[5]*(nums[5]-1)//2)*(nums[3]-2)
if nums[15] >= 1:
    ans += nums[15]*(nums[5]-1)
if nums[25] >= 1:
    ans += nums[25]*(nums[3]-1)
if nums[75] >= 1:
    ans += nums[75]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[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]
b=[0]*25
for i in range(1,n):
    m=i+1
    for j in a:
        while m%j==0:
            b[a.index(j)]+=1
            m//=j
sf=tf=ft=f=t=0
for i in b:
    if i>73:sf+=1
    if i>23:tf+=1
    if i>13:ft+=1
    if i>3:f+=1
    if i>1:t+=1
ans=sf
ans+=tf*(t-1)
ans+=ft*(f-1)
ans+=f*(f-1)*(t-2)//2
print(ans)

Submission status: Accepted

Solution code:
def prime_factors(n):
  seeds = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
  factors = []
  i = 0
  while i<=len(seeds)-1:
    if n % seeds[i]:
      i += 1
    else:
      n //= seeds[i]
      factors.append(seeds[i])
  return factors

def solve():
  N = int(input())
  
  factors = []
  for i in range(1, N+1):
    factors.extend(prime_factors(i))
  
  import collections
  c = collections.Counter(factors)
  lenc = len(c)
  
  n_1 = 0
  c1 = []
  for k, v in c.items():
    if v >= 74:
      n_1 += 1
      c1.append(k)
      
  # 14/4
  n_2 = 0
  c2=[]
  for k, v in c.items():
    if v < 14:
      continue
    for k2, v2 in c.items():
      if k == k2 or v2 < 4:
        continue
      n_2 += 1
      c2.append((k, k2))
     
  # 24/2
  n_3 = 0
  c3=[]
  for k, v in c.items():
    if v < 24:
      continue
    for k2, v2 in c.items():
      if k == k2 or v2 < 2:
        continue
      n_3 += 1
      c3.append((k, k2))
            
  # 4/4/2
  n_4 = 0
  c4=[]
  for k, v in c.items():
    if v < 2:
      continue
    for k2, v2 in c.items():
      if k == k2 or v2 < 4:
        continue
      for k3, v3 in c.items():
        if k == k3 or k2<=k3 or v3<4:
          continue
        n_4 += 1
        c4.append((k, k2, k3))
  print(n_1+n_2+n_3+n_4)
solve()

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

Solution code:
import math
N = int(input())

dic = dict() #素因数分解してつっこむリスト
def trial_division(n):
    tmp = int(math.sqrt(n)) + 1
    a = n
    for num in range(2, tmp):
        while n%num == 0: #割り切れる時
            if not num in dic:
                dic[num] = 1
            else:
                dic[num] += 1
            n //= num
    if n != 1:
        if not n in dic:
            dic[n] = 1
        else:
            dic[n] += 1

    return dic

# trial_division(5)
for i in range(2, N+1):
    trial_division(i)
    # print (i, dic)
    
# print (dic)
count = 0
for i in dic:
    if dic[i] >= 74:
        count += 1
    if dic[i] >= 24:
        for j in dic:
            if i != j and dic[j] >= 2:
                count += 1
    if dic[i] >= 14:
        for j in dic:
            if i != j and dic[j] >= 4:
                count += 1
    if dic[i] >= 4:
        for j in dic:
            if i < j and dic[j] >= 4:
                for k in dic:
                    if i != k and j != k and dic[k] >= 2:
                        count += 1

print (count)

Submission status: Accepted

Solution code:
primes = []
numberlist = []
for i in range(2, 101):
	numberlist.append(i)
while numberlist[0] <= 10:
	now = numberlist.pop(0)
	primes.append(now)
	newnumberlist = []
	for i in range(0, len(numberlist)):
		if numberlist[i]%now != 0:
			newnumberlist.append(numberlist[i])
	numberlist = newnumberlist
primes = primes + numberlist
counters = []
for i in range(0, len(primes)):
	counters.append(0)
N = int(input())
for i in range(1, N+1):
	m = i
	for j in range(0, len(primes)):
		while m % primes[j] == 0:
			counters[j] += 1
			m //= primes[j]
ans = 0
for i in range(0, len(primes)):
	if counters[i] >= 74:
		ans += 1
	for j in range(i+1, len(primes)):
		if counters[i] >= 2 and counters[j] >= 24:
			ans += 1
		if counters[j] >= 2 and counters[i] >= 24:
			ans += 1
		if counters[i] >= 4 and counters[j] >= 14:
			ans += 1
		if counters[j] >= 4 and counters[i] >= 14:
			ans += 1
		for k in range(j+1, len(primes)):
			if counters[i] >= 2 and counters[j] >= 4 and counters[k] >= 4:
				ans += 1
			if counters[i] >= 4 and counters[j] >= 2 and counters[k] >= 4:
				ans += 1
			if counters[i] >= 4 and counters[j] >= 4 and counters[k] >= 2:
				ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
N = math.factorial(n)
prime = [2]
for L in range(3,n):
    chk=True
    for L2 in prime:
        if L%L2 == 0:chk=False
    if chk==True:prime.append(L)
#print(prime)

cnt = []
for x in prime:
    l = N
    i = 0
    while 1:
        if l%x == 0:
            i += 1
            l //= x
        else:
            break
    cnt.append(i)
#print(cnt)

upper74 = 0
upper24 = 0
upper14 = 0
upper2 = 0
upper4 = 0
for x in cnt:
    if x >= 74:
        upper74 += 1
    if x >= 24:
        upper24 += 1
    if x >= 14:
        upper14 += 1
    if x >= 4:
        upper4 += 1
    if x >= 2:
        upper2 += 1
#print(upper2,upper4,upper24)
res = 0
#a**74タイプ
res += upper74
#a**2 * b**24　タイプ
res += (upper2 - 1)*upper24
#a**4 * b**14　タイプ
res += (upper4 - 1)*upper14
#a**2 * b**4 * c**4　タイプ
res += (upper4*(upper4 - 1)//2) * (upper2 - 2)
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())

d = defaultdict(int)
for i in range(1, n+1):
    j = 2
    while i > 1:
        if i % j == 0:
            d[j] += 1
            i = i // j
        else:
            j += 1

x = {75: 0, 25: 0, 15: 0, 5: 0, 3: 0}
for y in x:
    for v in d.values():
        if v + 1 >= y:
            x[y] += 1

ans = 0
ans += x[75]
ans += x[15] * (x[5] - 1) if x[5] >= 1 else 0
ans += x[25] * (x[3] - 1) if x[3] >= 1 else 0
ans += (x[5] * (x[5] - 1) // 2) * (x[3] - 2) if x[3] >= 2 else 0
print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
sieve = [True] * (n + 1)
for i in range(2, n+1):
    if sieve[i]:
        for j in range(i+i, n+1, i):
            sieve[j] = False

primes = [0] * (n+1)
for i in range(2, n+1):
    if sieve[i]:
        for j in range(i, n+1):
            j2 = j
            num = 0
            while j2 % i == 0:
                j2 /= i
                num += 1
            primes[i] += num
gt2 = 0
gt4 = 0
gt14 = 0
gt24 = 0
gt74 = 0
for i in range(2, n+1):
    if primes[i] >= 2:
        gt2 += 1
    if primes[i] >= 4:
        gt4 += 1
    if primes[i] >= 14:
        gt14 += 1
    if primes[i] >= 24:
        gt24 += 1
    if primes[i] >= 74:
        gt74 += 1
def nCk(n, k):
    numera = 1
    for i in range(n, n-k, -1):
        numera *= i
    denomi = 1
    for i in range(k, 0, -1):
        denomi *= i
    return numera / denomi
res = 0
res += gt14 * (gt4-1)
res += gt24 * (gt2-1)
res += gt74
res += nCk(gt4, 2)*(gt2-2)
print res

Submission status: Accepted

Solution code:
n = int(input())
table = [0] * (n + 1)
divider = 2
cnt = 0
able3 = 0
able5 = 0
able15 = 0
able25 = 0
able75 = 0

for i in range(1, n + 1):
    while True:
        if i == 1:
            divider = 2
            break
        elif i % divider == 0:
            table[divider] += 1
            i //= divider
        else:
            divider += 1

for i in table:
    if 2 <= i:
        able3 += 1
    if 4 <= i:
        able5 += 1
    if 14 <= i:
        able15 += 1
    if 24 <= i:
        able25 += 1
    if 74 <= i:
        able75 += 1

cnt += (able5 - 1) * able15  # 5 * 25
cnt += (able3 - 2) * (able5 - 1) * able5 // 2  # 3 * 5 * 5
cnt += (able3 - 1) * able25  # 25 * 3
cnt += able75  # 75
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
table = [0] * (n + 1)
divider = 2
cnt = 0
able3 = 0
able5 = 0
able15 = 0
able25 = 0
able75 = 0


def nCr(n, r):
    r = min(r, n-r)
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i
    return numerator // denominator


for i in range(1, n + 1):
    while True:
        if i == 1:
            divider = 2
            break
        elif i % divider == 0:
            table[divider] += 1
            i //= divider
        else:
            divider += 1

for i in table:
    if 2 <= i:
        able3 += nCr(2, i)
    if 4 <= i:
        able5 += nCr(4, i)
    if 14 <= i:
        able15 += nCr(14, i)
    if 24 <= i:
        able25 += nCr(24, i)
    if 74 <= i:
        able75 += nCr(74, i)

cnt += (able5 - 1) * able15  # 5 * 25
cnt += (able3 - 2) * (able5 - 1) * able5 // 2  # 3 * 5 * 5
cnt += (able3 - 1) * able25  # 25 * 3
cnt += able75  # 75
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

if N <= 9 :
    print(0)
else :
    primeCount = [0] * (N + 1)
    for i in range(2, N + 1) :
        current = i
        for j in range(2, i + 1) :
            while current % j == 0:
                primeCount[j] += 1
                current = current // j

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

    ans = 0
    ans += primeNum(75)
    ans += primeNum(25) * (primeNum(3) - 1)  # 3 には 25が含まれる
    ans += primeNum(15) * (primeNum(5) - 1)
    ans += primeNum(5) * (primeNum(5) - 1) * (primeNum(3) - 2) // 2
    print(ans)

Submission status: Accepted

Solution code:
ans = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 8, 8, 11, 11, 11, 11, 14, 14, 32, 32, 35, 35, 35, 35, 42, 42, 42, 42, 49, 49, 49, 49, 49, 49, 75, 75, 86, 86, 86, 86, 86, 86, 123, 123, 131, 131, 131, 131, 148, 148, 153, 153, 170, 170, 170, 170, 170, 170, 227, 227, 227, 227, 227, 227, 250, 250, 323, 323, 324, 324, 324, 324, 354, 354, 354, 354, 384, 384, 384, 384, 384, 391, 491, 491, 529, 529, 529, 529, 529, 529, 543]
print(ans[int(input())])

Submission status: Accepted

Solution code:
ans = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 8, 8, 11, 11, 11, 11, 14, 14, 32, 32, 35, 35, 35, 35, 42, 42, 42, 42, 49, 49, 49, 49, 49, 49, 75, 75, 86, 86, 86, 86, 86, 86, 123, 123, 131, 131, 131, 131, 148, 148, 153, 153, 170, 170, 170, 170, 170, 170, 227, 227, 227, 227, 227, 227, 250, 250, 323, 323, 324, 324, 324, 324, 354, 354, 354, 354, 384, 384, 384, 384, 384, 391, 491, 491, 529, 529, 529, 529, 529, 529, 543]
print(ans[int(input())])

Submission status: Accepted

Solution code:
N = int(input())
prime_number = [2, 3, 5, 7]
prim = [2, 3, 5, 7]

#素数作成
for i in range(2, 101):
	prime_flag = True
	for j in prim:
		if i % j == 0:
			prime_flag = False
			break
			
	if prime_flag:
		prime_number.append(i)
	
prime_factor = [0] * len(prime_number)

for i in range(2, N + 1):
	tmp = i
	for j in range(len(prime_number)):
		while tmp % prime_number[j] == 0:
			prime_factor[j] += 1
			tmp //= prime_number[j]
			
count2 = 0
count4 = 0
count14 = 0
count24 = 0
count74 = 0

for i in prime_factor:
	if i >= 2:
		count2 += 1
	if i >= 4:
		count4 += 1
	if i >= 14:
		count14 += 1
	if i >= 24:
		count24 += 1
	if i >= 74:
		count74 += 1

if count4 >= 2:		
	combination4 = count4 * (count4 - 1) // 2
else:
	combination4 = 0
	
ans = combination4 * (count2 - 2) + count14 * (count4 - 1) + count24 * (count2 - 1) + count74
print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(input())

def factorize(n):
  fac_dic={}
  for i in range(2,n):
    if i**2>n:
      break
      
    while(n%i==0):
      n//=i
      if i not in fac_dic:
        fac_dic[i]=1
      else:
        fac_dic[i]+=1

  if n!=1:
    fac_dic[n]=1    
  return fac_dic
        
if N==1:
  print(0)
  sys.exit()
  
fact_dic={}
for i in range(2,N+1):
  f_dic=factorize(i)
  for key in f_dic:
    if key in fact_dic:
      fact_dic[key]+=f_dic[key]
    else:
      fact_dic[key]=f_dic[key]
  
#print(fact_dic)
fact_list_n1=[]
for v in fact_dic.values():
  if v>1:
    fact_list_n1.append(v)
  
#print(fact_list_n1)
answer=0
for i in range(len(fact_list_n1)):
  if fact_list_n1[i]>=74:
    answer+=1
for i in range(len(fact_list_n1)):
  for j in range(len(fact_list_n1)):
    if i==j:
      continue      
    if fact_list_n1[i]>=14 and fact_list_n1[j]>=4:
      answer+=1
    if fact_list_n1[i]>=24 and fact_list_n1[j]>=2:
      answer+=1
for i in range(len(fact_list_n1)):
  for j in range(i+1,len(fact_list_n1)):
    for k in range(len(fact_list_n1)):
      if i==j or j==k or k==i:
        continue      
      if fact_list_n1[i]>=4 and fact_list_n1[j]>=4 and fact_list_n1[k]>=2:
        answer+=1

print(answer)

Submission status: Accepted

Solution code:
def num(v):
    return len(tuple(filter(lambda x: x >= v - 1, e)))


n = int(input())
e = [0] * (n + 1)

for i in range(2, n + 1):
    b = i
    j = 2
    while j * j <= i:
        while b % j == 0:
            b //= j
            e[j] += 1
        j += 1
    if b > 1:
        e[b] += 1
e = tuple(filter(lambda x: x > 0, e))

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

Submission status: Accepted

Solution code:
from collections import defaultdict


def cand_count(v, d):
    return len(tuple(filter(lambda x: x >= v, d.values())))


n = int(input())
d = defaultdict(int)

for i in range(2, n + 1):
    b = i
    j = 2
    while j * j <= i:
        while b % j == 0:
            b //= j
            d[j] += 1
        j += 1
    if b > 1:
        d[b] += 1
    # print(i, j, d)
# print(d)

ans = 0
ans += cand_count(74, d)
ans += cand_count(24, d) * (cand_count(2, d) - 1)
ans += cand_count(14, d) * (cand_count(4, d) - 1)
ans += cand_count(4, d) * (cand_count(4, d) - 1) // 2 * (cand_count(2, d) - 2)
print(ans)

Submission status: Accepted

Solution code:
#コピペ！！！
N = int(input())
e = [0]*(N+1)
for i in range(2, N+1):   #N!の素因数分解
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j
def num(m):              # e の要素のうち 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: Accepted

Solution code:
n = int(input())
lis=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
li=[]
a=0
b=0
c=0
d=0
e=0
for i in range(15):
    p=n
    q=0
    while(p>0):
        q+=p//lis[i]
        p=p//lis[i]
    if q>=74:
        e+=1
    if q>=24:
        a+=1
    if q>=14:
        b+=1
    if q>=4:
        c+=1
    if q>=2:
        d+=1
ans=a*(d-1)+b*(c-1)+(c*(c-1))//2*(d-2)+e
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def primes(m) :
    ps = [2]
    for i in range(3, m+1) :
        for p in ps :
            if i%p == 0 :
                break
        else :
            ps.append(i)
    return ps

def fdivisor(m) :
    ps = primes(m)
    df = {p:0 for p in ps}
    for i in range(1, m+1) :
        ii = i
        while ii != 1 :
            for p in ps :
                if ii%p == 0 :
                    df[p] += 1
                    ii //= p
    return df

ans = 0
df = fdivisor(n)
over2 = len([v for v in df.values() if v >= 2])
over4 = len([v for v in df.values() if v >= 4])
over14 = len([v for v in df.values() if v >= 14])
over24 = len([v for v in df.values() if v >= 24])
over74 = len([v for v in df.values() if v >= 74])
ans += over4*(over4-1)//2*(over2-2)
ans += over14*(over4-1)
ans += over24*(over2-1)
ans += over74

print(ans)

Submission status: Accepted

Solution code:
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 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]]

n = int(input())
l = primes(101)
d = {}
for i in l:
    d[i] = 0

for i in range(1,n+1):
    for k in factorize(i):
        d[k[0]] += k[1]

n2 = 0
n4 = 0
n14 = 0
n24 = 0
n74 = 0

for v in d.values():
    if v >= 2:
        n2 += 1
    if v >= 4:
        n4 += 1
    if v >= 14:
        n14 += 1
    if v >= 24:
        n24 += 1
    if v >= 74:
        n74 += 1

ans = 0
ans += (n4*(n4-1)//2)*(n2-2)
ans += n14*(n4-1)
ans += n24*(n2-1)
ans += n74
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

e = [0] * (n+1)


for i in range(2, n+1):
  num = i
  m = 2
  while m * m <= num:
    while num % m == 0:
      e[m] += 1
      num //= m
    m += 1
  if num > 1:
    e[num] += 1
    

num2 = num4 = num14 = num24 = num74 = 0    
for i in range(len(e)):
  if e[i] >= 2:
    num2 += 1
  if e[i] >= 4:
    num4 += 1
  
  if e[i] >= 14:
    num14 += 1
    
  if e[i] >= 24:
    num24 += 1
    
  if e[i] >= 74:
    num74 += 1
    
    
ans = num74 + (num24 * (num2-1)) + (num14 * (num4-1)) + (num4 * (num4-1) * (num2-2)//2)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
elecnt=[0]*len(prime)
for i in range(len(prime)):
  c=1
  while n>prime[i]**c:
    elecnt[i]+=n//(prime[i]**c)
    c+=1
above74=sum(1 for i in elecnt if i>=74)
above24=sum(1 for i in elecnt if i>=24)
above14=sum(1 for i in elecnt if i>=14)
above4=sum(1 for i in elecnt if i>=4)
above2=sum(1 for i in elecnt if i>=2)
print(above74+above24*(above2-1)+above14*(above4-1)+above4*(above4-1)*(above2-2)//2)

Submission status: Accepted

Solution code:
N = int(input())

d = dict()

for n in range(2, N+1):
    x = 2
    while n > 1:
        if n % x == 0:
            n //= x
            if x in d.keys():
                d[x] += 1
            else:
                d[x] = 1
        else:
            x += 1

# 75 = 3 * 5 * 5
# 75, 3 25, 5 15, 3 5 5 => 74, 2 24, 4 14, 2 4 4


def f(x):
    n = 0
    for i in d.values():
        if i >= x:
            n += 1
    return n


ans = f(74) + f(24) * (f(2) - 1) + f(14) * (f(4) - 1) \
      + ((f(4) * (f(4) - 1)) // 2) * (f(2) - 2)

print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    t = n
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while (t % i == 0):
            t //= i
            ret.append(i)
    if t > 1:
        ret.append(t)
    return ret


N = int(input())
d = []
for n in range(1, N + 1):
    d.extend(factorize(n))
d.sort()
ds = set(d)
dn = [0] * 101
for c in ds:
    dn[c] = d.count(c)
ans = 0
t = []
for i in ds:
    for j in ds:
        if i == j:
            continue
        for k in ds:
            if i == k or j == k:
                continue
            for l in [0, 2, 4, 14, 24, 74]:
                if l <= dn[i]:
                    for m in [0, 2, 4, 14, 24, 74]:
                        if m <= dn[j]:
                            for n in [0, 2, 4, 14, 24, 74]:
                                if n <= dn[k]:
                                    c = (l + 1) * (m + 1) * (n + 1)
                                    if c == 75:
                                        e = i ** l * j ** m * k ** n
                                        if not e in t:
                                            ans += 1
                                            t += [e]
print(ans)