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: Wrong Answer

Solution code:
from math import sqrt

def cnt_yakusu(num):
    sq_num = int(sqrt(num))
    cnt = 0
    for i in range(1, sq_num):
        for j in range(sq_num+1, num+1):
            if i*j==N:
                cnt += 2
    for i in range(350):
        if i**2 == num:
            cnt += 1
    return num

N = int(input())
ans = 0
for n in range(N, 1, -1):
    cnt = cnt_yakusu(n)
    if n == 75:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def factorize(N):  # 素因数分解
    p = 2 
    while p * p <= N:
        while N % p == 0:
            N //= p
            fact[p] += 1
        p += 1
    if N > 1:
        fact[N] += 1

n = int(input())
fact = defaultdict(int)
for i in range(n):
    factorize(i + 1)

cnt4 = sum(cnt >= 4 for cnt in fact.values())
cnt2 = sum(cnt >= 2 for cnt in fact.values())
cnt24 = sum(cnt >= 24 for cnt in fact.values())
cnt14 = sum(cnt >= 14 for cnt in fact.values())
cnt74 = sum(cnt >= 74 for cnt in fact.values())

ans = cnt4 * (cnt4 - 1) * (cnt2 - 2) // 2
ans += cnt24 * (cnt2 - 1) + cnt4 * cnt14 + cnt74
print(ans)

Submission status: Wrong Answer

Solution code:
P = [1 for _ in range(100)]
P[0]=0
P[1]=0
for i in range(2,11):
    for j in range(i**2,100,i):
        P[j] = 0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
N = int(input())
C = {p:0 for p in Q}
for i in range(2,N+1):
    for p in Q:
        if i%p==0:
            x = i
            while x%p==0:
                x = x//p
                C[p] += 1
cnt = 0
for p in Q:
    if C[p]>=74:
        cnt += 1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=2:
        cnt1 += 1
    if C[p]>=24:
        cnt2 += 1
cnt += (cnt2*(cnt2-1))//2+cnt2*(cnt1-cnt2)
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=4:
        cnt1 += 1
    if C[p]>=14:
        cnt2 += 1
cnt += (cnt2*(cnt2-1))//2+cnt2*(cnt1-cnt2)
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=2:
        cnt1 += 1
    if C[p]>=4:
        cnt2 += 1
cnt += (cnt2*(cnt2-1)*(cnt2-2))//6+((cnt2*(cnt2-1))//2)*(cnt1-cnt2)
print(cnt)

Submission status: Wrong Answer

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

N = int(input())
lis = [0] * 101
for i in range(1,N+1):
    prime_factorize(i,lis)
lis.sort()
ans = 0
for i in range(101):
    for j in range(i+1,101):
        for k in range(j+1,101):
            if lis[i] >= 2 and lis[j] >= 4:
                ans += 1
for i in range(101):
    for j in range(i+1,101):
        if lis[i] >= 4 and lis[j] >= 14:
            ans += 1
        if lis[i] >= 2 and lis[j] >= 24:
            ans += 1
for i in range(101):
    if lis[i] >= 74:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    d = defaultdict(int)
    #nまでの素数の配列を返す関数
    def primes(n):
        if n == 1:
            return []
        else:
            tbl = [True]*(n+1)
            pri = [2]
            for i in range(2,n+1,2):
                tbl[i] = False
            k = 3
            while k <= n:
                if tbl[k]:
                    pri.append(k)
                    for i in range(k,n+1,k):
                        tbl[i] = False
                k += 2
            return pri
    p = primes(n)
    for i in range(2,n+1):
        ii = i
        for j in p:
            while True:
                if ii%j == 0:
                    d[j] += 1
                    ii //= j
                else:
                    break
            if ii == 1:
                break
    d2 = 0
    d4 = 0
    d14 = 0
    d24 = 0
    for i in d.values():
        if i >= 2:
            d2 += 1
            if i >= 4:
                d4 += 1
                if i >= 14:
                    d14 += 1
                    if i >= 24:
                        d24 += 1

    print(d4*(d4-1)*(d2-2)//2+d14*(d4-1)+d24*(d2-1))

    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    prime = {}
    for i in range(2, n + 1):
        x = i
        for j in range(2, i + 1):
            while x % j == 0:
                if j not in prime:
                    prime[j] = 0
                prime[j] += 1
                x /= j
    a = [i for i in prime.values()]
    ans = 0
    for i in range(len(a)):
        for j in range(len(a)):
            for k in range(j, len(a)):
                ans += f(i, j, k, a)
    print(ans)


def f(i, j, k, a):
    if i == j & j == k:
        if a[i] >= 74:
            return 1
    elif i == j:
        if a[i] >= 14 & a[k] >= 4:
            return 1
    elif i == k:
        if a[i] >= 14 & a[j] >= 4:
            return 1
    elif j == k:
        if a[i] >= 2 & a[j] >= 24:
            return 1
    else:
        if a[i] >= 2 & a[j] >= 4 & a[k] >= 4:
            return 1
    return 0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def conb(n,r): 
    if n<r: return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_factorize(n):
    if n == 1:
        return [1]
    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 = inp()
d = defaultdict(int)
for i in range(1,n+1):
    for x in prime_factorize(i):
        d[x] += 1

valist = d.values()
c = [2,4,14,24,74]
cnt = [0] * 5
for x in valist:
    if x >= 74: cnt[4] += 1
    elif x >= 24: cnt[3] += 1
    elif x >= 14: cnt[2] += 1
    elif x >= 4: cnt[1] += 1
    elif x >= 2: cnt[0] += 1
res = 0
a = sum(cnt[1:]); b = cnt[0]
res += conb(a,3) + conb(a,2)*b
a = sum(cnt[2:]); b = cnt[1]
res += conb(a,2) + a*b
a = sum(cnt[3:]); b = sum(cnt[:3])
res += conb(a,2) + a*b
res += cnt[4]
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def conb(n,r): 
    if n<r: return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_factorize(n):
    if n == 1:
        return [1]
    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 = inp()
d = defaultdict(int)
for i in range(1,n+1):
    for x in prime_factorize(i):
        d[x] += 1

valist = d.values()
c = [2,4,14,24,74]
cnt = [0] * 5
for x in valist:
    if x >= 74: cnt[4] += 1
    elif x >= 24: cnt[3] += 1
    elif x >= 14: cnt[2] += 1
    elif x >= 4: cnt[1] += 1
    elif x >= 2: cnt[0] += 1
print(cnt)
res = 0
a = sum(cnt[1:]); b = cnt[0]
res += conb(a,3) + conb(a,2)*b
a = sum(cnt[2:]); b = cnt[1]
res += conb(a,2) + a*b
a = sum(cnt[3:]); b = sum(cnt[:3])
res += conb(a,2) + a*b
res += cnt[4]
print(res)

Submission status: Wrong Answer

Solution code:
# エラトステネスの篩
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append((p, c))
    return result


N = int(input())

prime_table = make_prime_table(100)

d = {}
for i in range(2, N + 1):
    for p, c in prime_factorize(i):
        d.setdefault(p, 0)
        d[prime_table[i]] += c

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
dp=[0]*(N+1)
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
for i in range(1,N+1):
  p=factorization(i)
  for x,y in p:
    dp[x]+=y
nplist=np.array(dp)
a=nplist[nplist>=2]
b=nplist[nplist>=4]
c=nplist[nplist>=14]
d=nplist[nplist>=24]
e=nplist[nplist>=74]
f=len(e)
g=len(d)*(len(a)-len(d))+len(d)*(len(d)-1)//2
h=len(c)*(len(b)-len(c))+len(c)*(len(c)-1)//2
k=len(b)*(len(b)-1)*(len(a)-len(b))//2+len(b)*(len(b)-1)*(len(b)-2)//6
print(f+g+h+k)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

def factorization(n):
    #arr = []
    #arr = defaultdict(int)
    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])
            arr[i] += cnt

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

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

    return arr

N =ii()
arr = defaultdict(int)

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

cnt = [0]*100

for key, value in arr.items():
    cnt[1] += 1
    cnt[value+1] += -1

cnt = list(accumulate(cnt))

ans = 0
#print(arr)
#print(cnt)
if cnt[4] > 1:
    #ans += cnt[4] * (cnt[2]-1) * (cnt[2]-2) // 2
    #ans += (cnt[2]-1) * (cnt[2]-2) // 2
    #ans = cnt[2] * (cnt[2]-1) // 2
    #ans += (cnt[2]-2)
    ans += cnt[4] * (cnt[4]-1) // 2 * (cnt[2]-cnt[4])
    ans += cnt[4] * (cnt[4]-1) * (cnt[4]-2) // 6

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

print(ans)

Submission status: Wrong Answer

Solution code:
# 60 -> {2:2, 3:1, 5:1}
def factorization(n):
    pf_cnt = {}
    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
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt


n = int(input())
prime_cnts = {}
for i in range(1,n+1):
    fac = factorization(i)
    for prime, cnt in fac.items():
        prime_cnts.setdefault(prime, 0)
        prime_cnts[prime] += cnt


cnt_75 = 0
cnt_25 = 0
cnt_15 = 0
cnt_5 = 0
cnt_3 = 0
for prime, cnt in prime_cnts.items():
    if cnt >= 75:
        cnt_75 += 1
    if cnt >= 25:
        cnt_25 += 1
    if cnt >= 15:
        cnt_25 += 1
    if cnt >= 5:
        cnt_5 += 1
    if cnt >= 3:
        cnt_5 += 1

ans = 0
ans += cnt_75
ans += cnt_15*cnt_5
ans += cnt_25*cnt_3
ans += cnt_3 * cnt_5*(cnt_5-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
import numpy as np
n = int(input())
dic = defaultdict(lambda : 0)
for i in range(2, n + 1):
    sqrt = math.floor(i ** 0.5)
    for j in range(2, sqrt + 1):
        if not i % j:
            count = 0
            while i % j == 0:
                count += 1
                i //= j
            dic[j] += count
    if i > 1:
        dic[i] += 1
values = np.array(list(dic.values()))
v1 = len(values[values >= 2])
v2 = len(values[values >= 4])
v = (v2 * (v2 - 1) // 2) * (v1 - 2)

v3 = len(values[values >= 24])
v += v3 * (v1 - 1)

v4 = len(values[values >= 14])
v += v4 * (v2 - 1)

v5 = len(values[values >= 75])
v += v5
print(v)

Submission status: Wrong Answer

Solution code:
N=int(input())
if N>=50:
    for i in range(10**100):
        print(i)

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

count=1
D=defaultdict(int)
for i in range(1,N+1):
    f=factorization(i)
    for t in f:
        num,con=t
        D[num]+=con
threes=0
fives=0
num_15=0
num_25=0
num_75=0

for v in D.values():
    if v>=2:
        threes+=1
    if v>=4:
        fives+=1
    if v>=14:
        num_15+=1
    if v>=24:
        num_25+=1
    if v>=74:
        num_75+=1
#3*5*5
ans=(threes-fives)*fives*(fives-1)//2
if fives>=3:
    ans+=cmb(fives, 3)
#75*1

ans+=num_75*(N-num_75)+num_75*(num_75-1)//2
#5*15

ans+=(fives-num_15)*(num_15-num_75)+(num_15-num_75)*(num_15-num_75)//2
#3*25
ans+=(threes-num_15)*(num_25-num_75)+(num_25-num_75)*(num_25-num_75)//2
print(ans)
#print(D)
#print(threes, fives, num_15, num_25, num_75)
#print(factorization(32400))

Submission status: Wrong Answer

Solution code:
N=int(input())


from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

count=1
D=defaultdict(int)
for i in range(1,N+1):
    f=factorization(i)
    for t in f:
        num,con=t
        D[num]+=con
threes=0
fives=0
num_15=0
num_25=0
num_75=0

for v in D.values():
    if v>=2:
        threes+=1
    if v>=4:
        fives+=1
    if v>=14:
        num_15+=1
    if v>=24:
        num_25+=1
    if v>=74:
        num_75+=1
#3*5*5
ans=(threes-fives)*fives*(fives-1)//2
if fives>=3:
    ans+=cmb(fives, 3)
#75*1

ans+=num_75*(N-num_75)+num_75*(num_75-1)//2
#5*15

ans+=(fives-num_15)*(num_15-num_75)+(num_15-num_75)*(num_15-num_75)//2
#3*25
ans+=(threes-num_15)*(num_25-num_75)+(num_25-num_75)*(num_25-num_75)//2
print(ans)
#print(D)
#print(threes, fives, num_15, num_25, num_75)
#print(factorization(32400))

Submission status: Wrong Answer

Solution code:
N=int(input())


from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

count=1
D=defaultdict(int)
for i in range(1,N+1):
    f=factorization(i)
    for t in f:
        num,con=t
        D[num]+=con
threes=0
fives=0
num_15=0
num_25=0
num_75=0

for v in D.values():
    if v>=2:
        threes+=1
    if v>=4:
        fives+=1
    if v>=14:
        num_15+=1
    if v>=24:
        num_25+=1
    if v>=74:
        num_75+=1
#3*5*5
ans=(threes-fives)*fives*(fives-1)//2
if fives>=3:
    ans+=cmb(fives, 3)
#75*1
ans+=num_75+(N-num_75)+num_75*(num_75-1)//2
#5*15
ans+=(fives-num_15)*(num_15-num_75)+(num_15-num_75)*(num_15-num_75)//2
#3*25
ans+=(threes-num_15)*(num_25-num_75)+(num_25-num_75)*(num_25-num_75)//2
print(ans)
#print(D)
#print(threes, fives, num_15, num_25, num_75)
#print(factorization(32400))

Submission status: Wrong Answer

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

def multiply_primes(a, b):
    """素因数分解系のCounter型のa, bに対してa*bの素因数分解系を計算する"""
    res = Counter([])
    keys = a.keys() | b.keys()
    for k in keys:
        res[k] = a[k] + b[k]
    return res

N = int(input())

# 答えは N! の約数かつ素因数分解が x^2 y^4 z^4 の形になるものしかないことに注意

f = Counter([])  # f が N! の素因数分解になる
for n in range(2, N+1):
    f = multiply_primes(f, Counter(prime_factorize(n)))

#print(f)

cand2 = [item for item in f.items() if (item[1] >= 2)]  # 指数部が2以上になるもの
cand4 = [item for item in f.items() if (item[1] >= 4)]  # 指数部が2以上になるもの

#print(cand2, cand4)

# cand4 から2つ、cand2 から1つ選ぶ（ただし cand2 で選ぶのは cand4 で選ばれてないもの）
ans = (len(cand4) * (len(cand4)-1))//2 * (len(cand2) - 2)
print(ans)

Submission status: Wrong Answer

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

def multiply_primes(a, b):
    """素因数分解系のCounter型のa, bに対してa*bの素因数分解系を計算する"""
    res = Counter([])
    keys = a.keys() | b.keys()
    for k in keys:
        res[k] = a[k] + b[k]
    return res

N = int(input())

# 答えは N! の約数かつ素因数分解が x^2 y^4 z^4 の形になるものしかないことに注意

f = Counter([])  # f が N! の素因数分解になる
for n in range(2, N+1):
    f = multiply_primes(f, Counter(prime_factorize(n)))

print(f)

cand2 = [item for item in f.items() if (item[1] >= 2)]  # 指数部が2以上になるもの
cand4 = [item for item in f.items() if (item[1] >= 4)]  # 指数部が2以上になるもの

print(cand2, cand4)

# cand4 から2つ、cand2 から1つ選ぶ（ただし cand2 で選ぶのは cand4 で選ばれてないもの）
ans = (len(cand4) * (len(cand4)-1))//2 * (len(cand2) - 2)
print(ans)

Submission status: Wrong Answer

Solution code:
##昨日やった...
import numpy as np

def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

factors = [0]*100
N = int(input())

for i in range(1,N+1):
    for p,n in prime_factorize(i):
        factors[p] += n

factors = np.array(factors)
ov2 = len(factors[factors >= 2])
ov4 = len(factors[factors >= 4])
ov14 = len(factors[factors >= 14])
ov24 = len(factors[factors >= 24])
ov74 = len(factors[factors >= 74])
print(ov2,ov4,ov14,ov24)
ans = 0
## 2*4*4
ans += (ov4-2)*(ov4)*(ov4-1)//2 + (ov2-ov4)*(ov4)*(ov4-1)//2

## 14 * 4
ans += (ov4-ov14)*(ov14) + (ov14)*(ov14-1)

## 24 * 2
ans += (ov2-ov24)*ov24 + (ov24)*(ov24-1)

## 74
ans += ov74

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

li = []

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

from collections import Counter

c = Counter(li)

kumi = [0]*101

for i,j in c.items():
    kumi[j] += 1
point = 0
#553
point += kumi[2]*(sum(kumi[4:])*(sum(kumi[4:])-1)//2)
#15 5
point += kumi[4]*sum(kumi[14:])
#25 3
point += kumi[3]*sum(kumi[24:])
#75
point += kumi[74]

print(point)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc114/tasks/abc114_d
# https://betrue12.hateblo.jp/entry/2018/12/02/224027
# https://coonevo.hatenablog.com/entry/2020/03/18/192431

from collections import defaultdict

MAX_N = 101

def solve():
    n = int(input())
    # 2 ~ 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

    primes = []
    for i in range(n + 1):
        if e[i] > 0:
            primes.append(i)

    # p^74になるやつ
    ans = 0
    for p in primes:
        if e[p] >= 75:
            ans += 1
    
    # p^2 q^24 (3 * 25) と p^4 * q^14 (5 * 15)
    for p in primes:
        for q in primes:
            if p == q:
                continue
            if e[p] >= 4 and e[q] >= 14:
                ans += 1
            if e[p] >= 2 and e[q] >= 24:
                ans += 1

    # p^2 q^4 r^4 (3 x 5 x 5)
    for p in primes:
        for q in primes:
            for r in primes:
                if r <= q:
                    continue
                if p == q or r == p:
                    continue
                if e[p] >= 2 and e[q] >= 4 and e[r] >= 4:
                    ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import factorial
from itertools import product


def get_divisors(n):
    div = []
    append = div.append
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            append(i)
            if i != n // i:
                append(n // i)
    div.sort()
    return div 


# input
N = int(input())
N_fact = factorial(N)

if N_fact < 357:
    print(0)
else:
    Nf_dig = len(str(N_fact))
    divisors = get_divisors(N_fact)
    dig = 3
    sgs_nuns = []
    sgs = ["7", "5", "3"]
    set_sgs = set(sgs)
    str_join = "".join
    for n in range(3, Nf_dig + 1):
        sgs_nuns += [
            str_join(n)
            for n in product(["7", "5", "3"], repeat=n)
            if set(str_join(n)) == set_sgs and int(str_join(n)) in divisors
        ]

    cnt = len(sgs_nuns)
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    N = int(input())
    if N < 10: return 0
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())

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

print(prime_fact(n))

def eratosthenes(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]]
p=eratosthenes(100)
d={}
for p_i in p:
    d[p_i]=0
for i in range(2,n+1):
    pf=prime_fact(i)
    for pf_i in pf:
        d[pf_i]+=1
print(d)

cnt74=0
cnt24=0
cnt14=0
cnt4=0
cnt2=0

for key in d:
    if d[key]>=74:
        cnt74+=1
    if d[key]>=24:
        cnt24+=1
    if d[key]>=14:
        cnt14+=1
    if d[key]>=4:
        cnt4+=1
    if d[key]>=2:
        cnt2+=1

print(cnt74,cnt24,cnt14,cnt4,cnt2)

print(int(cnt74+(cnt2-1)*cnt24+(cnt4-1)*cnt14+(cnt2-2)*cnt4*(cnt4-1)/2))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
lst = {}
for num in prime:
    lst[num] = 0
for i in range(1, n + 1):
    for num in lst:
        while i % num == 0:
            i //= num
            lst[num] += 1
        if i < num:
            break
        
more_2 = 0
more_4 = 0
more_14 = 0
more_24 = 0
more_74 = 0
for i, j in lst.items():
    if j >= 2:
        more_2 += 1
    if j >= 4:
        more_4 += 1
    if j >= 14:
        more_14 += 1
    if j >= 24:
        more_24 += 1
    if j >= 74:
        more_74 += 1
ans = 0
if more_24 >= 1:
    ans += more_24 * (more_2 - 1)
if more_14 >= 1:
    ans += more_14 * (more_4 - 1)
if more_4 >= 2:
    ans += (more_4 * (more_4 - 1)) // 2 * (more_2 - 2)
if more_74 >= 1:
    ans += more_74
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
lst = {}
for num in prime:
    lst[num] = 0
for i in range(1, n + 1):
    for num in lst:
        while i % num == 0:
            i //= num
            lst[num] += 1
        if i < num:
            break
        
more_2 = 0
more_4 = 0
more_14 = 0
more_24 = 0
more_74 = 0
for i, j in lst.items():
    if j >= 2:
        more_2 += 1
    if j >= 4:
        more_4 += 1
    if j >= 14:
        more_14 += 1
    if j >= 24:
        more_24 += 1
    if j >= 74:
        more_74 += 1
ans = 0
if more_24 >= 1:
    ans += more_24 * (more_2 - 1)
if more_14 >= 1:
    ans += more_14 * (more_4 - 1)
if more_4 >= 2:
    ans += more_4 * (more_4 - 1) // 2 * (more_2 - 2)
if more_74 >= 1:
    ans += more_74
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
def fact(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

from collections import defaultdict
d = defaultdict(int)
for i in range(1,n+1):
    for itm in fact(i):
        if itm[0]!=1:
            d[itm[0]]+=itm[1]
keys = d.keys()
ans = set()
for p in keys:
    if d[p]>=74:
        ans.add(p**d[p])
    for q in keys:
        if p==q:
            continue
        if d[p] >=2 and d[q]>=24:
            ans.add(p**d[p] * q**d[q])
        if d[p] >=4 and d[q]>=14:
            ans.add(p**d[p] * q**d[q])
        for r in keys:
            if q==r or r==p:
                continue
            if d[p] >=2 and d[q]>=4 and d[r]>=4:
                ans.add(p**d[p] * q**d[q] * r**d[r])

print(len(ans))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
lis = [0] * n
for i in range(2,n+1):
    now = i
    for j in range(2,math.ceil(math.sqrt(i))+1):
        while now % j == 0:
            now //= j
            lis[j-1] += 1
    if now != 1:
        lis[now-1] += 1

  # print(lis)

ans = 0

two = 0
four = 0
fourteen = 0
twentyfour = 0
seventyfour = 0
for num in lis:
    if num >= 74:
        seventyfour += 1
    if num >= 24:
        twentyfour += 1
    if num >= 14:
        fourteen += 1
    if num >= 4:
        four += 1
    if num >= 2:
        two += 1

ans += seventyfour

if twentyfour >= 2:
    ans += (twentyfour * (twentyfour - 1))//2

if twentyfour:
    ans += twentyfour * (two -twentyfour)

if fourteen:
    ans += fourteen * (four -fourteen)

if two and four >= 2:
    ans += (two -four) * ((four) * (four - 1)) // 2

  # print(ans)

if four >= 3:
    ans += (four * (four - 1) * (four - 2)) // 3

print(ans)