AtCoder ABC114参戦記

ABCの３完、D問題は終了後4分で通りました。Cに1時間近く時間をかけてしまったのが情けないところ。個人的に難易度はD < Cでした。先にDを解くべきだった。

以下提出コード

C問題 (755)

N = int(input())
LN = list(map(int, str(N)))
dig = len(LN)
Ans = 0
 
if N <= 99:print(0)
else:
    Ans += 0
    if N >= 1000:
        for i in range(3, dig):
            Ans += 3**i - 3 * 2**i + 3
    def base3(i, dig):
        t = i
        lt = []
        while t > 0:
            lt.append(t%3)
            t //= 3
        while len(lt) < dig:
            lt.append(0)
        out = 0
        for i in range(dig):
            out *= 10
            out += (3 if lt[i] == 0 else 5 if lt[i]==1 else 7)
        return out
    for i in range(3**dig + 1):
        num = base3(i, dig)
        if len(set(str(num))) == 3 and num <= N: Ans += 1
    print(Ans)

入力された整数Nの桁をdigNとします。i桁(3~digN-1桁)の3, 5, 7のみを使う整数は各桁の取り方が3通りあるので総数は3ⁱ個です。そこから二種類の数字しか使わない整数の総数2ⁱ個(3通りあります)を引いた後、引きすぎた33･･･3, 555･･･5, 777･･･7を足しなおします。

digN桁の753数は全探索で求めます。今回は最大で9桁なので3⁹個、すなわち19683個の整数の判定となり、十分に間に合います。0 ~ 19683を三進数に変換し、各桁の数字が０，１，２のときそれぞれ３，５，７に置き換えます。あとはNより大きいかどうかと使っている数字が3種類かどうかを判定して数えていきます。

D問題 (756)

N = int(input())
lim = 1
for i in range(N): lim *= (i+1)
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]
 
Ans = 0
for i in range(23):
    for j in range(i+1, 24):
        for k in range(j+1, 25):
            a, b, c = Prime[i], Prime[j], Prime[k]
            d, e, f = (a**4)*(b**4)*(c**2), (a**4)*(b**2)*(c**4), (a**2)*(b**4)*(c**4)
            if d <= lim and lim%d == 0: Ans += 1
            if e <= lim and lim%e == 0: Ans += 1
            if f <= lim and lim%f == 0: Ans += 1
for i in range(24):
    for j in range(i+1, 25):
        a, b = Prime[i], Prime[j]
        d, e, f, g = (a**24)*(b**2), (a**2)*(b**24), (a**4)*(b**14), (a**14)*(b**4)
        if d <= lim and lim%d == 0: Ans += 1
        if e <= lim and lim%e == 0: Ans += 1
        if f <= lim and lim%f == 0: Ans += 1
        if g <= lim and lim%g == 0: Ans += 1
for i in range(5):
    if Prime[i] ** 74 <= lim and lim % (Prime[i]**74) == 0: Ans += 1
print(Ans)

かなりの力技で解きましたが実行時間的には余裕でした。基本的に公式の解説と考察自体は同じです。約数が75個ということで、七五数Iの素因数をp, q, rとすると、Iとなるのはp⁴q⁴r²、p²q¹⁴、p⁷⁴のみです。あとは適当に素数を当てはめて実際にN!以下になり、N!の約数になるものを探していけばいいです。急いでいたため100以下の素数をすべて列挙していますが、実際には50以下で十分です。