結果

問題 No.3087 幸せな家族と除け者たち
ユーザー furafura
提出日時 2023-09-13 18:12:19
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,382 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-07-01 02:50:28
合計ジャッジ時間 602 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
10,496 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def is_prime(n: int) -> bool:
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


def prime_factorize(n: int) -> list[tuple[int, int]]:
    res = []
    p = 1
    while n > 1:
        p += 1
        if not is_prime(p):
            continue
        e = 0
        while n % p == 0:
            e += 1
            n //= p
        res.append((p, e))
    return res


def pretty(pf: list[tuple[int, int]]) -> str:
    return ' '.join(str(e) for p, e in pf)


# https://oeis.org/A001228
O = [7920, 95040, 175560, 443520, 604800, 10200960, 44352000, 50232960, 244823040, 898128000, 4030387200, 145926144000, 448345497600, 460815505920, 495766656000, 42305421312000, 64561751654400, 273030912000000, 51765179004000000, 90745943887872000, 4089470473293004800, 4157776806543360000, 86775571046077562880, 1255205709190661721292800, 4154781481226426191177580544000000, 808017424794512875886459904961710757005754368000000000]
assert len(O) == 26

x = 433536485242324290468617700417455364450827766781149222360763650909761367389882988885139582203840750697595829714068587820137806573020739031914050848405080498961121956355636199276360499200000000000000000000000000000000000000000000
# print(f'x : {pretty(prime_factorize(x))}')
# for i in range(26):
#     print(f'{chr(ord("A") + i)} : {pretty(prime_factorize(O[i]))}')

# x : 205 96 44 26 14 5 3 9 6 1 7 1 1 0 2 0 1 0 1 1
# A :   4  2  1  0  1
# B :   6  3  1  0  1
# C :   3  1  1  1  1 0 0 1
# D :   7  2  1  1  1
# E :   7  3  2  1
# F :   7  2  1  1  1 0 0 0 1
# G :   9  2  3  1  1
# H :   7  5  1  0  0 0 1 1
# I :  10  3  1  1  1 0 0 0 1
# J :   7  6  3  1  1
# K :  10  3  2  3  0 0 1
# L :  14  3  3  1  0 1 0 0 0 1
# M :  13  7  2  1  1 1
# N :   9  4  1  3  1 0 0 1 0 0 1
# O :  10  7  3  1  1 0 0 0 1
# P :  18  6  3  1  1 0 0 0 1
# Q :  17  9  2  1  1 1
# R :  14  6  6  1  1 0 0 1
# S :   8  7  6  1  1 0 0 0 0 0 1 1 0 0 0 0 0 0 1
# T :  15 10  3  2  0 1 0 1 0 0 1
# U :  18 13  2  1  1 1 1 0 1
# V :  21  9  4  2  1 1 0 0 1
# W :  21  3  1  1  3 0 0 0 1 1 1 1 0 1
# X :  21 16  2  3  1 1 1 0 1 1
# Y :  41 13  6  2  1 1 1 1 1 0 1 0 0 0 1
# Z :  46 20  9  6  2 3 1 1 1 1 1 0 1 0 1 0 1 0 0 1

C = ['Z', 'Y', 'S', 'T', 'N', 'N', 'N', 'O', 'O', 'I', 'I', 'C', 'H', 'R', 'A']
for c in C:
    i = ord(c) - ord('A')
    assert x % O[i] == 0, i
    x //= O[i]
assert x == 1

print('synchronization')
0