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


class Prime:
    seed_primes = [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]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


#prime = Prime()
#prime.find_factors(36610051291281) == {653: 1, 593783: 1, 3: 3, 13: 1, 269: 1}

## ある数Mが"75数"であるとき、Mの素因数分解した時の各素因数の数(a,b,c,...)は
## (74),(24,2),(14,4),(4,4,2) ...(*)
## のどれかである（必要十分）
## つまり与えられたNに対して、N!を素因数分解し、その素因数を(*)の組だけ持ってこれる総数が答え

## 参考: ABC052-C

def ABC114D_74(lst):
  return len([1 for x in lst if x >= 74])

def ABC114D_24_2(lst):
  var1 = len([1 for x in lst if x >= 24])
  var2 = len([1 for x in lst if x >= 2])
  return var1 * (var2-1)

def ABC114D_14_4(lst):
  var1 = len([1 for x in lst if x >= 14])
  var2 = len([1 for x in lst if x >= 4])
  return var1 * (var2-1)

def ABC114D_4_4_2(lst):
  var1 = len([1 for x in lst if x >= 4])
  var2 = len([1 for x in lst if x >= 2])
  return ((var1*(var1-1))//2) * (var2-2)


from collections import Counter

N = int(input())

prime = Prime()

solver_dict = {}
for i in range(N):
  pre_dict = prime.find_factors(i+1)
  solver_dict = dict(Counter(solver_dict) + Counter(pre_dict))

lst = list(solver_dict.values())
#print(lst)

var1 = ABC114D_74(lst)
var2 = ABC114D_24_2(lst)
var3 = ABC114D_14_4(lst)
var4 = ABC114D_4_4_2(lst)
ans = var1 + var2 + var3 + var4
#print(var1, var2, var3, var4)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l_prm = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
l_prm = [i for i in l_prm if i<=n/2]
l_new = []
for i in l_prm:
    a = n
    counter = 0
    b = a
    c=1
    while b!=0:
        b = a//i**c
        counter += b
        c += 1
    l_new.append(counter)
ans=0
def num(j,lst):
    return(len([i for i in lst if i>=j]))
ans += num(4,l_new) * (num(4,l_new)-1)/2 *(num(2,l_new)-2)
ans += num(14,l_new)*(num(4,l_new)-1)
ans += num(24,l_new)*(num(2,l_new)-1)
ans += num(74,l_new)
print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())

bit = [0]*(N+1)

for i in range(2,N+1):
    cur = i
    for j in range(2,i+1):
        while cur%j==0:
            bit[j]+=1
            cur//=j

def nu(m):
    return len(list(filter(lambda x:x>=m-1,bit)))
#75, 25 3, 5 5 3, 15 5, 

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

Submission status: Accepted

Solution code:
N=int(input())
def prime_factorization(n):
    r={}
    for i in range(2,int(n**.5)+1):
        num=0
        while(True):
            x,y=divmod(n,i)
            if y!=0:
                break
            n=x
            num+=1
        if num>0:
            r[i]=num
    if n>1:
        r[n]=1
    return r
D={}
for i in range(N):
    d=prime_factorization(i+1)
    for k in d.keys():
        if k in D:
            D[k]+=d[k]
        else:
            D[k]=d[k]
c=[0]*5
for v in D.values():
    if v>73:
        c[0]+=1
    if v>23:
        c[1]+=1
    if v>13:
        c[2]+=1
    if v>3:
        c[3]+=1
    if v>1:
        c[4]+=1
print(c[0]+c[1]*max(0,c[4]-1)+c[2]*max(0,c[3]-1)+c[3]*max(0,c[3]-1)*max(0,c[4]-2)//2)

Submission status: Accepted

Solution code:
n=int(input())
l={}
if n<=9:
  print(0)
else:
  for i in range(2,n+1):
    x=i
    for j in range(2,i+1):
      while x%j==0:
      	if j in l:
        	l[j]+=1
      	else:
        	l[j]=1
      	x=x//j
  c=0
  if l[2]>=74:
    c+=1
  c3=0
  c5=0
  c25=0
  c15=0
  for i in l:
    if l[i]>=2:
      c3+=1
      if l[i]>=4:
        c5+=1
        if l[i]>=14:
          c15+=1
          if l[i]>=24:
            c25+=1
  print(c5*(c5-1)*(c3-2)//2+c25*(c3-1)+c15*(c5-1)+c)

Submission status: Accepted

Solution code:
N = int(input())

# N!の約数で約数をちょうど75個持つものは何個あるか
primes = []
primes4 = []
primes14 = []
primes24 = []
primes74 = []
for x in range(2,N//2+1):
    isPrime = True
    for i in range(2, x):
        if x % i == 0:
            isPrime = False
            break
    if isPrime:
        primes.append(x)


for p in primes:
    cnt = 0
    for i in range(1, 7):
        cnt += N // (p ** i)
    if cnt >= 74:
        primes74.append(p)
    if cnt >= 24:
        primes24.append(p)
    if cnt >= 14:
        primes14.append(p)
    if cnt >=4:
        primes4.append(p)



res = 0
n = len(primes)
n4 = len(primes4)
n14 = len(primes14)
n24 = len(primes24)
n74 = len(primes74)

# 3,25のパターン
res += (n-1)*n24

# 75のパターン
res += n74

# 3,5,5のパターン
if n4 >= 2:
    res += (n - 2) * n4 * (n4 - 1) // 2

# 5, 15 のパターン
if n14 > 0:
    res += (n4-1)*n14

print(res)

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
cnt=defaultdict(int)
for i in range(1,1+N):
    now=i
    for j in range(2,i+1):
        if now<j:
            break
        while now%j==0:
            cnt[j]+=1
            now//=j
ans=0
for i,vi in cnt.items():
    if vi>=74:
        ans+=1
    if vi>=24:
        for j,vj in cnt.items():
            if i==j:continue
            elif vj>=2:
                ans+=1
    if vi>=14:
        for j,vj in cnt.items():
            if i==j:continue
            elif vj>=4:
                ans+=1
    if vi>=2:
        for j,vj in cnt.items():
            if i==j:
                continue
            for k,vk in cnt.items():
                if i==k:
                    continue
                if j<k and vj>=4 and vk>=4:
                    ans+=1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
d = {}
for n in range(2,N+1):
    i = 2
    while i <= n:
        while n % i == 0:
            n //= i
            if i not in d:
                d[i] = 0
            d[i] += 1
        i += 1

ans_d = {3:0,5:0,15:0,25:0,75:0}    

for p in d:
    for n in ans_d:    
        if d[p] >= n-1:
            ans_d[n] += 1

ans = ans_d[5]*(ans_d[5]-1)*(ans_d[3]-2)//2+ans_d[75]

for n1 in ans_d:
    for n2 in ans_d:
        if n1 < n2 and n1*n2 == 75:
            ans += ans_d[n2]*(ans_d[n1]-1)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
prime_list = [0] * (N+1)
cnt=0
for i in range(2, N + 1):
    cnt = 2
    copy=i
    while (cnt ** 2 <= copy):
        if (copy % cnt == 0):
            prime_list[cnt] += 1
            copy = int(copy / cnt)
            
        else:
            cnt += 1
    prime_list[copy] += 1
#ここまではok??　nまでの素因数を格納していく感じ!
cnt3 = 0
cnt5 = 0
cnt15 = 0
cnt25 = 0
cnt75 = 0
for i in range(1, N + 1):
    if (prime_list[i] >= 2):
        cnt3 += 1
    if (prime_list[i] >= 4):
        cnt5 += 1
    if (prime_list[i] >= 14):
        cnt15 += 1
    if (prime_list[i] >= 24):
        cnt25 += 1
    if (prime_list[i] >= 74):
        cnt75 += 1
#ここでは75=3*5*5だから各素因数が何個あるか取り出したいよね。これを必要なところだけ取っていく

#print(cnt75+ cnt25*(cnt3-1)+cnt15*(cnt5-1)+int((cnt5-1)*cnt5/2)*(cnt3-2))       
#こういうことなんだけど一つ一つ説明します笑

a = cnt75
#これはx^74となる数のこと
b = cnt25 * (cnt3 - 1)
#これはx^24*y^2となる数のことなんだけでcnt3にはxも含まれてるよね(というのも上で>=のかたちで数えてるから)
# だから自分の分を引かなきゃだめーって感じ!!
c=cnt15*(cnt5-1)
#これもおなじだよね、うん、、笑
d = int((cnt5-1)*cnt5/2)*(cnt3-2)
#ここも同じなんだけどまずx^4*y^4*z^2の形がほしいんだからcnt5の中から2つ欲しい、つまりnC2の関係を使ってもとめる、このあとz^2はcnt2のなかから取るんだけど
#この中には当然x,yがはいってるからその分の2を引いたものをかける感じ！！　これらをすべて足せばok!!笑

print(a+b+c+d)

Submission status: Accepted

Solution code:
N = int(input())
prime_list = [0] * (N+1)
cnt=0
for i in range(2, N + 1):
    cnt = 2
    copy=i
    while (cnt ** 2 <= copy):
        if (copy % cnt == 0):
            prime_list[cnt] += 1
            copy = int(copy / cnt)
            
        else:
            cnt += 1
    prime_list[copy] += 1
#ここまではok??　nまでの素因数を格納していく感じ!
cnt3 = 0
cnt5 = 0
cnt15 = 0
cnt25 = 0
cnt75 = 0
for i in range(1, N + 1):
    if (prime_list[i] >= 2):
        cnt3 += 1
    if (prime_list[i] >= 4):
        cnt5 += 1
    if (prime_list[i] >= 14):
        cnt15 += 1
    if (prime_list[i] >= 24):
        cnt25 += 1
    if (prime_list[i] >= 74):
        cnt75 += 1
#ここでは75=3*5*5だから各素因数が何個あるか取り出したいよね。これを必要なところだけ取っていく

#print(cnt75+ cnt25*(cnt3-1)+cnt15*(cnt5-1)+int((cnt5-1)*cnt5/2)*(cnt3-2))       
#こういうことなんだけど一つ一つ説明します笑

a = cnt75
#これはx^74となる数のこと
b = cnt25 * (cnt3 - 1)
#これはx^24*y^3となる数のことなんだけでcnt3にはxも含まれてるよね(というのも上で>=のかたちで数えてるから)
# だから自分の分を引かなきゃだめーって感じ!!
c=cnt15*(cnt5-1)
#これもおなじだよね、うん、、笑
d = int((cnt5-1)*cnt5/2)*(cnt3-2)
#ここも同じなんだけどまずx^5*y^5*z^2の形がほしいんだからcnt5の中から2つ欲しい、つまりnC2の関係を使ってもとめる、このあとz^2はcnt2のなかから取るんだけど
#この中には当然x,yがはいってるからその分の2を引いたものをかける感じ！！　これらをすべて足せばok!!笑

print(a+b+c+d)

Submission status: Accepted

Solution code:
from collections import defaultdict

def trial_division(n):

    tmp = int(n ** 0.5) + 1
    for num in range(2, tmp):
        while n % num == 0:
            d[num] += 1
            n //= num
    if n > 1:
        d[n] += 1

    return

N = int(input())

d = defaultdict(int)

for i in range(1, N+1):
    trial_division(i)

a = 0
b = 0
c = 0
x = 0
y = 0

for k, v in d.items():
    if v + 1 >= 3:
        a += 1
    if v + 1 >= 5:
        b += 1
    if v + 1 >= 15:
        c += 1
    if v + 1 >= 25:
        x += 1
    if v + 1 >= 75:
        y += 1

ans = (a-2) * ((b * (b-1)) // 2) + (b-1) * c + x * (a-1) + y
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    n = int(input())
    prime = [0 for _ in range(n + 1)]
    for i in range(1, n + 1):
        num = i
        for j in range(2, i + 1):
            while num % j == 0:
                num /= j
                prime[j] += 1
    ans = 0
    for i in range(2, n + 1):
        if prime[i] >= 74:
            ans += 1
        for j in range(i + 1, n + 1):
            if prime[i] >= 24 and prime[j] >= 2:
                ans += 1
            if prime[i] >= 14 and prime[j] >= 4:
                ans += 1
            if prime[i] >= 4 and prime[j] >= 14:
                ans += 1
            if prime[i] >= 2 and prime[j] >= 24:
                ans += 1
            for k in range(j + 1, n + 1):
                if prime[i] >= 2 and prime[j] >= 4 and prime[k] >= 4:
                    ans += 1
                if prime[i] >= 4 and prime[j] >= 2 and prime[k] >= 4:
                    ans += 1
                if prime[i] >= 4 and prime[j] >= 4 and prime[k] >= 2:
                    ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
N=int(input())
p=[]
q=dict()
for i in range(2,N+1):
    for j in p:
        if i%j==0:
            break
    else:
        p.append(i)
for i in p:
    q[i]=0
for i in range(1,N+1):
    for j in p:
        for k in range(6,0,-1):
            if i%(j**k)==0:
                q[j]+=k
                break
r=list(q.values())
cnt_74,cnt_24,cnt_14,cnt_4,cnt_2=0,0,0,0,0
for i in r:
    if i>=74:
        cnt_74+=1
    if i>=24:
        cnt_24+=1
    if i>=14:
        cnt_14+=1
    if i>=4:
        cnt_4+=1
    if i>=2:
        cnt_2+=1
print(cnt_74+cnt_24*(cnt_2-1)+cnt_14*(cnt_4-1)+cnt_4*(cnt_4-1)*(cnt_2-2)//2)

Submission status: Accepted

Solution code:
n = int(input())


def main(n):
    prime = [0 for _ in range(n + 1)]
    for i in range(2, n + 1):
        for j in range(2, n + 1):
            if j > i:
                break
            while i % j == 0:
                i //= j
                prime[j] += 1
    e2 = 0
    e4 = 0
    e14 = 0
    e24 = 0
    e74 = 0
    for i in range(2, n + 1):
        if prime[i] >= 2:
            e2 += 1
        if prime[i] >= 4:
            e4 += 1
        if prime[i] >= 14:
            e14 += 1
        if prime[i] >= 24:
            e24 += 1
        if prime[i] >= 74:
            e74 += 1
    ret = e74
    if e2 > 2 and e4 > 1:
        ret += e4 * (e4 - 1) // 2 * (e2 - 2)
    if e4 > 1 and e14 > 0:
        ret += e14 * (e4 - 1)
    if e2 > 0 and e4 > 0:
        ret += e24 * (e2 - 1)

    return ret


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

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

table = makelist(101, 101)
for num in range(1, N+1):
    for i in range(2, 100):
        table[num][i] = table[num-1][i]

    n = num
    div = 2
    while n > 1:
        if n % div == 0:
            table[num][div] += 1
            n //= div
        else:
            div += 1

primes = []
for i in range(2, 100):
    flag = True
    for e in primes:
        if i % e == 0:
            flag = False
            break
    if flag:
        primes.append(i)

l = len(primes)
memo = table[N]
ans = 0

for e1 in primes:
    for e2 in primes:
        for e3 in primes:
            if e1 != e2 and e2 != e3 and e1 != e3 and memo[e1] >= 4 and memo[e2] >= 4 and memo[e3] >= 2:
                ans += 1

ans //= 2
for e in primes:
    if memo[e] >= 74:
        ans += 1
for e1 in primes:
    for e2 in primes:
        if e1 != e2 and memo[e1] >= 24 and memo[e2] >= 2:
            ans += 1
for e1 in primes:
    for e2 in primes:
        if e1 != e2 and memo[e1] >= 14 and memo[e2] >= 4:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
p=[0 for i in range(n+1)]
for i in range(2,n+1):
    t=2
    a=i
    while t<=10:
        if(a%t==0):
            p[t]+=1
            a//=t
        else:
            t+=1
    p[a]+=1
d={2:0,4:0,14:0,24:0,74:0}
for i in p[2:]:
    if(i>=2):
        d[2]+=1
    if(i>=4):
        d[4]+=1
    if(i>=14):
        d[14]+=1
    if(i>=24):
        d[24]+=1
    if(i>=74):
        d[74]+=1
print((d[2]-2)*d[4]*(d[4]-1)//2+(d[4]-1)*d[14]+(d[2]-1)*d[24]+d[74])

Submission status: Accepted

Solution code:
N = int(input())

prime_array = [
    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
]
prime_count = [0] * 25

for n in range(1, N + 1):
    for i, j in enumerate(prime_array):
        if n < j:
            break
        while n % j == 0:
            prime_count[i] += 1
            n = n / j

# print(prime_count)

can_use_count = [0] * 5  # 2,4,14,24,74

for i in prime_count:
    if i >= 2:
        can_use_count[0] += 1
    if i >= 4:
        can_use_count[1] += 1
    if i >= 14:
        can_use_count[2] += 1
    if i >= 24:
        can_use_count[3] += 1
    if i >= 74:
        can_use_count[4] += 1

ans = 0
ans += can_use_count[4]  # a^74
ans += can_use_count[3] * (can_use_count[0] - 1)  # a^24 * b^2
ans += can_use_count[2] * (can_use_count[1] - 1)  # a^14 * b^4
ans += can_use_count[1] * (
    can_use_count[1] - 1) / 2 * (can_use_count[0] - 2)  # a^4 * b^4 * c^2

print(int(ans))

Submission status: Accepted

Solution code:
s = int(input())

def prime(R):
    s = 0
    prime_list = []
    while s==0:
        for i in range(2,R+1):
            if R%i==0:
                R=R//i
                if R==1:
                    s=1
                prime_list.append(i)
                break
    return prime_list
prime_list = []
for i in range(2,s+1):
    for p in prime(i):
        prime_list.append(p)
uniq = list(set(prime_list))
prime_counts = []
for u in uniq:
    if prime_list.count(u) != 1:
        prime_counts.append(prime_list.count(u))
c74 = 0
c24 = 0
c14 = 0
c4 = 0
for pc in prime_counts:
    if pc >= 74:
        c74 += 1
        c24 += 1
        c14 += 1
        c4 += 1
    elif pc >= 24:
        c24 += 1
        c14 += 1
        c4 += 1
    elif pc >= 14:
        c14 += 1
        c4 += 1
    elif pc >= 4:
        c4 += 1

ans = 0
ans += c74
ans += c24*(len(prime_counts)-1)
ans += c14*(c4-1)
ans += c4*(c4-1)*(len(prime_counts)-2)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N=input()

Parts=defaultdict(lambda: 0)

for i in range(1,N+1):
	num_sqrt=int(i**0.5)+2

	for n in range(2,num_sqrt):
		while i%n==0:
			i/=n
			Parts[n]+=1
	else:
		if i!=1:
			Parts[i]+=1


C=defaultdict(lambda: set()) 
for val,cnt in  Parts.items():
	#print val,cnt
	if 0<=cnt: C[1].add(val)
	if 2<=cnt: C[3].add(val)
	if 4<=cnt: C[5].add(val)
	if 14<=cnt: C[15].add(val)
	if 24<=cnt: C[25].add(val)
	if 74<=cnt: C[75].add(val)

ans=0
#25,3
for x in C[25]:
	for y in C[3]:
		if x!=y:	ans+=1

#15,5
for x in C[15]:
	for y in C[5]:
		if x!=y:	ans+=1

#5,5,3
for x in C[5]:
	for y in C[5]:
		for z in C[3]:
			if x<y and x!=z and y!=z:	ans+=1

#75
ans+=len(C[75])

print ans

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np
 
def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 
# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
# 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):
    cnt = 0
    for ei in e:
        if ei >= m-1:
            cnt += 1
    return cnt

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:
# -*- coding: utf-8 -*-
"""
D - 756
https://atcoder.jp/contests/abc114/tasks/abc114_d

"""
import sys


from collections import Counter

def prime_factor(N):
    factors = Counter()
    for i in range(2, int(N**0.5)+1):
        while N % i == 0:
            factors[i] += 1
            N //= i
    if N != 1:
        factors[N] = 1
    return factors


def solve(n):
    d = Counter()
    for i in range(2, n+1):
        x = prime_factor(i)
        d += x
    t3 = [v for k, v in d.items() if v >= 2]
    t5 = [v for k, v in d.items() if v >= 4]
    t15 = [v for k, v in d.items() if v >= 14]
    t25 = [v for k, v in d.items() if v >= 24]
    t75 = [v for k, v in d.items() if v >= 74]
    ans = len(t75) + len(t25)*(len(t3)-1) + len(t15)*(len(t5)-1)+len(t5)*(len(t5)-1)*(len(t3)-2) // 2
    return ans


def main(args):
    n = int(input())
    ans = solve(n)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
d = ddict(int)
n = int(input())
for i in range(1,n+1):
  for p in range(2,int(i**.5)+2):
    while i%p == 0:
      d[p] += 1
      i//=p
  if i>1:
    d[i] += 1
g = [2,4,14,24,74]
f = [0]*5
for x in d.values():
  for i in range(5):
    if x >= g[i]:
      f[i] += 1
ans = f[1]*(f[1]-1)//2*(f[0]-2) + f[3]*(f[0]-1) + f[2]*(f[1]-1) + f[4]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
x = defaultdict(int)
for i in range(2, n + 1):
    k = i
    for j in range(2, i + 1):
        while(k % j == 0):
            k = k // j
            x[j] += 1

y = defaultdict(int)
for i in x.values():
    for j in [2, 4, 14, 24, 74]:
        if i >= j:
            y[j] += 1

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

Submission status: Accepted

Solution code:
def sol():
    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)

    ans=0
    for i in range(n+1):
        if e[i]>73: ans+=1


    for i in range(n):
        for j in range(i+1,n+1):
            if e[i]>23 and e[j]>1: ans+=1
            if e[i]>1 and e[j]>23: ans+=1

    for i in range(n):
        for j in range(i+1,n+1):
            if e[i]>13 and e[j]>3: ans+=1
            if e[i]>3 and e[j]>13: ans+=1

    for i in range(n-1):
        for j in range(i+1,n):
            for k in range(j+1,n+1):
                if e[i]>3 and e[j]>3 and e[k]>1: ans+=1
                if e[i]>3 and e[j]>3 and e[k]>3: ans+=1
                if e[i]>1 and e[j]>3 and e[k]>3: ans+=1
    print(ans)

if __name__=="__main__":
    sol()

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:
from collections import defaultdict
from itertools import chain


def fast_prime_set(n):
    # nまでの素数リスト高速版 setで返す
    # chainの読み込みが必要！
    if n < 4:
        return ({}, {}, {2}, {2, 3})[n]
    n_sqrt = int(n ** 0.5) + 1
    primes = {2, 3} | set(chain(range(5, n + 1, 6), range(7, n + 1, 6)))
    for i in range(5, n_sqrt, 2):
        if i in primes:
            primes.difference_update(range(i * i, n, i * 2))
    return primes


def prime_factorization(x):
    # 素因数分解
    # 事前に素数のセットが必要
    primes = fast_prime_set(100)

    fact = defaultdict(int)
    for prime in primes:
        while x % prime == 0:
            fact[prime] += 1
            x //= prime
        if x == 1:
            break
        if x in primes:
            fact[x] += 1
            break
    return fact


n = int(input())
div_c = defaultdict(int)

for i in range(1, n+1):
    for item, cnt in prime_factorization(i).items():
        div_c[item] += cnt

div_c[1] = 0
cnt_div = defaultdict(int)

for c in div_c.values():
    for j in [2,4,14,24,74]:
        cnt_div[j] += c >= j

ans = 0
if cnt_div[4]:
    ans += cnt_div[4] * (cnt_div[4] - 1) // 2 * (cnt_div[2] - 2)
ans += cnt_div[14] * (cnt_div[4] - 1)
ans += cnt_div[24] * (cnt_div[2] - 1)
ans += cnt_div[74]

print(ans)

Submission status: Accepted

Solution code:
def prime(n):
  if n==1:
    return False
  elif n==2 or n==3:
    return True
  else:
    for i in range(2,int(n**0.5)+1):
      if n%i==0:
        return False
    else:
      return True

n=int(input())
cnt=[0]*(n+1)
for i in range(1,n+1):
  tmp=i
  for j in range(1,i+1):
    if prime(j):
      if tmp%j==0:
        cnt[j]+=1
        tmp=tmp//j
        while tmp%j==0:
          cnt[j]+=1
          tmp=tmp//j
c74=0
c24=0
c14=0
c4=0
c2=0
for i in range(n+1):
  if cnt[i]>=74:
    c74+=1
  elif cnt[i]>=24:
    c24+=1
  elif cnt[i]>=14:
    c14+=1
  elif cnt[i]>=4:
    c4+=1
  elif cnt[i]>=2:
    c2+=1
ans=0
ans+=c74
ans+=(c74+c24)*(c74+c24+c14+c4+c2-1)
ans+=(c74+c24+c14)*(c74+c24+c14+c4-1)
ans+=(((c74+c24+c14+c4)*(c74+c24+c14+c4-1))//2)*(c74+c24+c14+c4+c2-2)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc114/tasks/abc114_d

import itertools
from collections import Counter
from collections import defaultdict
import bisect

def solve(primes, index, target):
    if index == len(primes):
        if target == 1:
            return 1
        else:
            return 0
    ans = 0
    for i in range(primes[index] + 1):
        if target % (i + 1) != 0:
            continue
        ans += solve(primes, index + 1, target // (i + 1))

    return ans



def main():
    N = int(input())
    primes = [0] * (N + 1)

    for i in range(N + 1):
        cur = i
        for j in range(2, i + 1):
            while cur % j == 0:
                primes[j] += 1
                cur //= j

    # print(primes)
    print(solve(primes, 0, 75))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import defaultdict
n=int(input())
a=[0]*100
d=defaultdict(int)
def div(x):
    for i in range(2,int(x**0.5)+2):
        while x%i==0:
            x//=i
            d[i]+=1
    if x!=1:
        d[x]+=1

for i in range(2,n+1):
    div(i)

ans=0
s=set()
for i in d.keys():
    if d[i]>=74:
        ans+=1
        s.add(i**74)
    for j in d.keys():
        if j==i:
            continue
        if all([d[i]>=14,d[j]>=4]):
            ans+=1
            s.add(i**14*j**4)
        if all([d[i]>=24,d[j]>=2]):
            ans+=1
            s.add(i**24*j**2)
        for k in d.keys():
            if k==j or k==i:
                continue
            if all([d[i]>=2,d[j]>=4,d[k]>=4]):
                ans+=1
                s.add(i**2*j**4*k**4)
print(len(s))

Submission status: Accepted

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

n = int(input())
e = [0]*(n+1)
for i in range(2,n+1):
    t = i
    for j in range(2,i+1):
        while t%j == 0:
            e[j] += 1
            t //= 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:
from math import sqrt, ceil, factorial
def is_prime(num):
  for i in range(2, ceil(sqrt(num))+1):
    if num%i==0:
      return False
  return True

def permcnt(n, r):
  return factorial(n) // factorial(n-r)

def combcnt(n, r):
  return factorial(n) // (factorial(n-r)*factorial(r))

n = int(input())
pls = [2]
i=3
while i<=n:
  if is_prime(i):
    pls.append(i)
  i+=1

def factoring(num):
  return _factoring(num, dict())
  
def _factoring(num, p):
  for i in pls:
    if num % i == 0:
      if i in p:
        p[i] += 1
      else:
        p[i] = 1
      return _factoring(num//i, p)
  return p

factors = dict()
for i in range(1,n+1):
  for k, v in factoring(i).items():
    if k in factors:
      factors[k] += v
    else:
      factors[k] = v

cnt = 0

# 七五数がx^74の形となるケース
cnt += len(list(filter(lambda x:x[1]>=74, factors.items())))

# 七五数がx^2*y^24の形となるケース
xs = {k for k,v in factors.items() if 2<=v and v<24}
ys = {k for k,v in factors.items() if v>=24}
cnt += len(xs)*len(ys)
cnt += permcnt(len(ys), 2) if len(ys)>=2 else 0

# 七五数がx^4*y^14の形となるケース
xs = {k for k,v in factors.items() if 4<=v and v<14}
ys = {k for k,v in factors.items() if v>=14}
cnt += len(xs)*len(ys)
cnt += permcnt(len(ys), 2) if len(ys)>=2 else 0

# 七五数がx^2*y^5*z^5の形となるケース
xs = {k for k,v in factors.items() if 2<=v and v<4}
ys = {k for k,v in factors.items() if v>=4}
cnt += len(xs)*combcnt(len(ys),2) if len(ys)>=2 else 0
cnt += 3*combcnt(len(ys), 3) if len(ys)>=3 else 0

print(cnt)