結果

問題 No.719 Coprime
ユーザー maspymaspy
提出日時 2020-05-09 22:20:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 32 ms / 3,000 ms
コード長 11,922 bytes
コンパイル時間 92 ms
コンパイル使用メモリ 13,696 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2024-07-06 05:03:26
合計ジャッジ時間 3,053 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
11,904 KB
testcase_01 AC 28 ms
11,904 KB
testcase_02 AC 28 ms
11,904 KB
testcase_03 AC 30 ms
11,776 KB
testcase_04 AC 30 ms
11,904 KB
testcase_05 AC 30 ms
11,776 KB
testcase_06 AC 27 ms
11,776 KB
testcase_07 AC 27 ms
11,776 KB
testcase_08 AC 27 ms
11,904 KB
testcase_09 AC 27 ms
11,776 KB
testcase_10 AC 27 ms
11,776 KB
testcase_11 AC 27 ms
11,776 KB
testcase_12 AC 28 ms
11,904 KB
testcase_13 AC 27 ms
11,904 KB
testcase_14 AC 27 ms
11,776 KB
testcase_15 AC 28 ms
11,776 KB
testcase_16 AC 27 ms
11,776 KB
testcase_17 AC 28 ms
11,776 KB
testcase_18 AC 28 ms
11,904 KB
testcase_19 AC 28 ms
11,904 KB
testcase_20 AC 28 ms
11,904 KB
testcase_21 AC 31 ms
11,776 KB
testcase_22 AC 29 ms
11,776 KB
testcase_23 AC 29 ms
11,776 KB
testcase_24 AC 30 ms
11,776 KB
testcase_25 AC 31 ms
11,776 KB
testcase_26 AC 32 ms
11,904 KB
testcase_27 AC 31 ms
12,032 KB
testcase_28 AC 31 ms
11,904 KB
testcase_29 AC 29 ms
11,904 KB
testcase_30 AC 28 ms
11,904 KB
testcase_31 AC 28 ms
11,776 KB
testcase_32 AC 28 ms
11,904 KB
testcase_33 AC 28 ms
12,032 KB
testcase_34 AC 27 ms
11,904 KB
testcase_35 AC 27 ms
11,776 KB
testcase_36 AC 28 ms
11,776 KB
testcase_37 AC 28 ms
11,776 KB
testcase_38 AC 29 ms
11,904 KB
testcase_39 AC 30 ms
11,776 KB
testcase_40 AC 29 ms
11,776 KB
testcase_41 AC 28 ms
12,032 KB
testcase_42 AC 30 ms
11,904 KB
testcase_43 AC 29 ms
11,904 KB
testcase_44 AC 29 ms
11,904 KB
testcase_45 AC 29 ms
12,032 KB
testcase_46 AC 27 ms
11,904 KB
testcase_47 AC 28 ms
11,776 KB
testcase_48 AC 27 ms
11,904 KB
testcase_49 AC 27 ms
11,776 KB
testcase_50 AC 28 ms
11,776 KB
testcase_51 AC 28 ms
11,776 KB
testcase_52 AC 27 ms
11,776 KB
testcase_53 AC 26 ms
11,776 KB
testcase_54 AC 27 ms
11,776 KB
testcase_55 AC 28 ms
11,776 KB
testcase_56 AC 29 ms
11,904 KB
testcase_57 AC 28 ms
11,904 KB
testcase_58 AC 27 ms
12,032 KB
testcase_59 AC 28 ms
11,776 KB
testcase_60 AC 27 ms
11,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
def solve(N):
    if N < 2:
        return 0
    import numpy as np
    import networkx as nx
    import itertools

    def make_prime(U):
        is_prime = np.zeros(U + 1, dtype=np.bool)
        is_prime[2] = 1
        is_prime[3::2] = 1
        for p in range(3, U + 1):
            if p * p > U:
                break
            if is_prime[p]:
                is_prime[p * p::2 * p] = 0
        return is_prime.nonzero()[0]

    def separete_LU(primes, U):
        max_lower = U // primes
        bl = (max_lower[:-1] <= max_lower[1:] + 1)
        idx = np.nonzero(~bl)[0].max() + 1
        upper = primes[idx:]
        lower = primes[:idx]
        return lower, upper

    def calc_wt(N, p, q, pow_p):
        max_composite = max(x * y for x in pow_p[p] for y in pow_p[q]
                            if x * y <= N)
        wt = max_composite - pow_p[p][-1] - pow_p[q][-1]
        return wt

    def create_graph(N, lower, upper, pow_p):
        V = set()
        E = []
        for p, q in itertools.combinations(lower, 2):
            wt = calc_wt(N, p, q, pow_p)
            if wt <= 0:
                continue
            V.add(p)
            V.add(q)
            E.append((p, q, wt))
        for p in lower:
            for pp in pow_p[p][1:]:
                n = N // pp
                # n以下の最大素数を上側集合からとる
                if n < upper[0]:
                    continue
                q = upper[upper <= n].max()
                wt = pp * q - pow_p[p][-1] - q
                if wt <= 0:
                    continue
                V.add(p)
                V.add(q)
                E.append((p, q, wt))

        G = nx.Graph()
        G.add_nodes_from(V)
        for a, b, c in E:
            G.add_edge(a, b)
            G.edges[a, b]['weight'] = c
        return G

    primes = make_prime(N)
    lower, upper = separete_LU(primes, N)
    pow_p = dict()
    for p in lower:
        pow_p[p] = [1]
        while pow_p[p][-1] <= N // p:
            pow_p[p].append(pow_p[p][-1] * p)
    G = create_graph(N, lower, upper, pow_p)
    matching = nx.max_weight_matching(G)
    S = sum(x[-1] for x in pow_p.values())
    S += upper.sum()
    S += sum(G.edges[a, b]['weight'] for a, b in matching)
    return S


A = [0, 0, 2, 5, 7, 12, 12, 19, 23, 29, 29, 40, 40
     ] + [solve(n) for n in range(13, 1300)]
str(A)
"""

A = [
    0, 0, 2, 5, 7, 12, 12, 19, 23, 29, 29, 40, 40, 53, 53, 54, 62, 79, 79, 98,
    98, 102, 102, 125, 125, 145, 145, 158, 163, 192, 192, 223, 234, 234, 234,
    237, 237, 274, 274, 274, 274, 315, 315, 358, 359, 359, 359, 406, 406, 445,
    445, 452, 458, 511, 511, 530, 530, 534, 534, 593, 593, 654, 654, 654, 679,
    687, 687, 754, 754, 762, 762, 833, 833, 906, 906, 906, 906, 923, 923, 1002,
    1002, 1037, 1037, 1120, 1120, 1136, 1136, 1136, 1136, 1225, 1225, 1250,
    1250, 1250, 1250, 1258, 1258, 1355, 1355, 1355, 1355, 1456, 1456, 1559,
    1561, 1561, 1561, 1668, 1668, 1777, 1777, 1777, 1777, 1890, 1890, 1906,
    1921, 1925, 1925, 1961, 1961, 2071, 2071, 2071, 2077, 2110, 2110, 2237,
    2272, 2272, 2272, 2403, 2403, 2415, 2415, 2415, 2415, 2552, 2552, 2691,
    2691, 2691, 2691, 2691, 2691, 2691, 2691, 2691, 2691, 2840, 2840, 2991,
    2991, 3032, 3032, 3032, 3032, 3189, 3189, 3189, 3189, 3218, 3218, 3381,
    3381, 3381, 3381, 3548, 3548, 3695, 3695, 3706, 3707, 3880, 3880, 3880,
    3880, 3880, 3880, 4059, 4059, 4240, 4240, 4240, 4240, 4263, 4263, 4312,
    4324, 4324, 4324, 4515, 4515, 4708, 4708, 4708, 4708, 4905, 4905, 5104,
    5104, 5104, 5104, 5160, 5160, 5176, 5176, 5188, 5188, 5208, 5208, 5419,
    5437, 5437, 5437, 5445, 5445, 5457, 5457, 5457, 5457, 5492, 5492, 5715,
    5715, 5715, 5715, 5942, 5942, 6171, 6171, 6171, 6215, 6448, 6448, 6464,
    6464, 6464, 6464, 6703, 6703, 6944, 6944, 7003, 7003, 7003, 7003, 7007,
    7009, 7009, 7009, 7260, 7260, 7320, 7320, 7320, 7371, 7628, 7628, 7664,
    7664, 7664, 7664, 7927, 7927, 7951, 7951, 7951, 7951, 8220, 8220, 8491,
    8491, 8491, 8491, 8491, 8491, 8768, 8768, 8773, 8773, 9054, 9054, 9337,
    9337, 9337, 9337, 9361, 9361, 9633, 9633, 9633, 9633, 9926, 9926, 9950,
    9953, 9953, 9953, 9961, 9961, 9973, 9973, 9973, 9973, 9981, 9981, 10288,
    10288, 10288, 10288, 10599, 10599, 10912, 10912, 10912, 10912, 11229,
    11229, 11355, 11355, 11355, 11355, 11355, 11355, 11355, 11355, 11355,
    11372, 11396, 11396, 11727, 11727, 11775, 11775, 11799, 11799, 12136,
    12136, 12136, 12136, 12156, 12156, 12217, 12231, 12231, 12231, 12578,
    12578, 12927, 12927, 12927, 12927, 13280, 13280, 13296, 13296, 13296,
    13296, 13655, 13655, 13982, 13982, 13982, 13982, 13990, 13990, 14357,
    14357, 14389, 14389, 14389, 14389, 14762, 14762, 14762, 14790, 14878,
    14878, 15257, 15257, 15257, 15257, 15640, 15640, 15640, 15640, 15656,
    15656, 16045, 16045, 16108, 16108, 16108, 16108, 16132, 16132, 16529,
    16529, 16529, 16529, 16930, 16930, 16934, 16934, 16934, 16934, 17014,
    17014, 17423, 17423, 17423, 17423, 17434, 17434, 17450, 17450, 17450,
    17450, 17869, 17869, 18290, 18290, 18302, 18364, 18364, 18364, 18376,
    18376, 18376, 18376, 18807, 18807, 19240, 19240, 19240, 19240, 19240,
    19240, 19679, 19679, 19679, 19679, 20122, 20122, 20146, 20146, 20146,
    20146, 20595, 20595, 20635, 20635, 20635, 20635, 20635, 20635, 21092,
    21092, 21092, 21092, 21553, 21553, 22016, 22080, 22080, 22080, 22547,
    22547, 22583, 22583, 22583, 22583, 22603, 22603, 22603, 22603, 22651,
    22651, 23130, 23130, 23202, 23202, 23202, 23202, 23234, 23234, 23721,
    23721, 23721, 23721, 24212, 24212, 24353, 24353, 24353, 24391, 24415,
    24415, 24914, 24914, 24914, 24914, 25417, 25417, 25433, 25433, 25433,
    25433, 25942, 25942, 25954, 26001, 26001, 26001, 26009, 26009, 26049,
    26049, 26049, 26049, 26570, 26570, 27093, 27093, 27093, 27093, 27125,
    27125, 27578, 27578, 27626, 27626, 27674, 27674, 27690, 27690, 27690,
    27690, 27690, 27690, 28231, 28231, 28231, 28231, 28239, 28239, 28786,
    28786, 28802, 28802, 28963, 28963, 28999, 28999, 28999, 28999, 29556,
    29556, 29580, 29580, 29580, 29580, 30143, 30143, 30159, 30159, 30159,
    30159, 30728, 30728, 31299, 31299, 31299, 31299, 31299, 31299, 31876,
    31876, 31876, 31876, 31900, 31900, 31960, 31960, 31960, 31960, 32547,
    32547, 32551, 32551, 32551, 32594, 33187, 33187, 33187, 33187, 33187,
    33187, 33786, 33786, 34387, 34387, 34435, 34435, 34435, 34435, 35042,
    35042, 35042, 35042, 35090, 35090, 35703, 35703, 35703, 35703, 36320,
    36320, 36939, 36939, 36939, 36939, 36975, 36975, 37148, 37148, 37148,
    37148, 37233, 37233, 37864, 37905, 37905, 37905, 37905, 37905, 37905,
    37905, 37937, 37937, 38578, 38578, 39221, 39221, 39221, 39221, 39868,
    39868, 39928, 39928, 39928, 39928, 40581, 40581, 40581, 40643, 40659,
    40659, 41318, 41318, 41979, 41979, 41979, 41979, 41979, 41979, 42088,
    42088, 42088, 42088, 42108, 42108, 42781, 42781, 42781, 42781, 43458,
    43458, 43506, 43506, 43506, 43506, 44189, 44189, 44189, 44189, 44189,
    44219, 44291, 44291, 44982, 44982, 44982, 44982, 44982, 44982, 45046,
    45046, 45046, 45046, 45747, 45747, 45855, 45855, 45855, 45855, 45879,
    45879, 46588, 46588, 46636, 46636, 46680, 46680, 46680, 46680, 46680,
    46680, 47399, 47399, 47411, 47411, 47411, 47411, 47482, 47482, 48209,
    48209, 48306, 48306, 48316, 48316, 49049, 49049, 49049, 49049, 49109,
    49109, 49848, 49848, 49848, 49848, 50591, 50591, 50591, 50591, 50591,
    50591, 50615, 50615, 51366, 51448, 51448, 51448, 51448, 51448, 52205,
    52205, 52205, 52205, 52966, 52966, 52978, 52978, 52978, 52978, 53050,
    53050, 53819, 53819, 53819, 53819, 54592, 54592, 54596, 54596, 54596,
    54596, 54668, 54668, 54708, 54708, 54708, 54708, 54708, 54708, 55495,
    55495, 55495, 55495, 55519, 55519, 55543, 55543, 55543, 55543, 56340,
    56340, 56378, 56378, 56378, 56378, 56398, 56398, 56398, 56398, 56398,
    56426, 57235, 57235, 58046, 58046, 58046, 58046, 58046, 58046, 58082,
    58082, 58082, 58082, 58903, 58903, 59726, 59740, 59740, 59740, 60567,
    60567, 61396, 61396, 61396, 61396, 61396, 61396, 61396, 61396, 61397,
    61397, 62236, 62236, 63015, 63015, 63015, 63015, 63015, 63015, 63015,
    63089, 63089, 63089, 63298, 63298, 64151, 64151, 64151, 64151, 65008,
    65008, 65867, 65867, 65867, 65867, 66730, 66730, 66754, 66754, 66754,
    66754, 66814, 66814, 66886, 66886, 66908, 66908, 66908, 66908, 67785,
    67785, 67785, 67785, 68666, 68666, 69549, 69549, 69549, 69549, 70436,
    70436, 70520, 70520, 70520, 70520, 70528, 70528, 70530, 70530, 70530,
    70530, 70530, 70530, 70658, 70658, 70658, 70686, 70694, 70694, 71601,
    71601, 71630, 71630, 72541, 72541, 72581, 72581, 72581, 72581, 72605,
    72605, 73524, 73524, 73524, 73524, 73572, 73572, 73577, 73577, 73593,
    73593, 74522, 74522, 74522, 74522, 74522, 74522, 74522, 74522, 75459,
    75459, 75459, 75459, 76400, 76400, 76647, 76741, 76741, 76741, 77688,
    77688, 77712, 77712, 77712, 77712, 78665, 78665, 78665, 78665, 78665,
    78665, 78701, 78701, 79604, 79604, 79636, 79636, 79636, 79636, 80603,
    80603, 80603, 80603, 81574, 81574, 81586, 81586, 81586, 81616, 82593,
    82593, 82653, 82653, 82669, 82669, 83652, 83652, 83652, 83652, 83652,
    83652, 83696, 83696, 84687, 84687, 84687, 84687, 84687, 84687, 85684,
    85684, 85684, 85684, 85684, 85684, 85780, 85780, 85780, 85780, 85888,
    85888, 86897, 86897, 86897, 86897, 87910, 87910, 87910, 87910, 87942,
    87942, 88961, 88961, 89982, 89982, 89982, 90091, 90245, 90245, 90317,
    90317, 90317, 90317, 91348, 91348, 92381, 92381, 92381, 92381, 92413,
    92413, 93452, 93452, 93452, 93452, 93512, 93512, 93512, 93512, 93512,
    93512, 94561, 94561, 95612, 95612, 95612, 95612, 95612, 95612, 95624,
    95624, 95624, 95624, 96685, 96685, 97748, 97748, 97748, 97748, 97828,
    97828, 98897, 98897, 98897, 98897, 99034, 99034, 99038, 99038, 99038,
    99038, 99086, 99086, 99218, 99218, 99218, 99218, 99218, 99218, 100305,
    100305, 100305, 100305, 101396, 101396, 102489, 102489, 102489, 102489,
    103586, 103586, 103622, 103622, 103622, 103622, 104725, 104725, 104725,
    104725, 104887, 104887, 105996, 105996, 106036, 106036, 106036, 106036,
    106036, 106036, 107153, 107153, 107153, 107153, 107261, 107261, 108384,
    108384, 108384, 108384, 108384, 108384, 109513, 109513, 109513, 109513,
    109533, 109533, 109533, 109574, 109574, 109574, 109670, 109670, 109706,
    109706, 109706, 109706, 109706, 109706, 109706, 109706, 109706, 109706,
    110857, 110857, 112010, 112010, 112010, 112010, 112082, 112082, 112118,
    112118, 112122, 112122, 113285, 113285, 113285, 113285, 113285, 113315,
    113339, 113339, 114510, 114510, 114510, 114510, 114522, 114522, 114562,
    114562, 114562, 114562, 115743, 115743, 115743, 115743, 115743, 115743,
    116930, 116930, 117165, 117165, 117165, 117165, 118358, 118358, 118358,
    118358, 118358, 118358, 118378, 118378, 119579, 119579, 119579, 119579,
    119579, 119579, 119643, 119643, 119643, 119643, 119679, 119679, 120892,
    120892, 120892, 120892, 122109, 122109, 122399, 122399, 122399, 122399,
    123622, 123622, 123622, 123622, 123622, 123622, 124851, 124851, 126082,
    126082, 126082, 126082, 126082, 126082, 127319, 127319, 127319, 127319,
    127321, 127321, 127361, 127361, 127361, 127361, 127395, 127395, 128644,
    128644, 128660, 128660, 128696, 128696, 128696, 128730, 128730, 128730,
    129989, 129989, 130085, 130085, 130085, 130171, 130171, 130171, 130183,
    130183, 130183, 130183, 130303, 130303, 130411, 130411, 130411, 130411,
    131688, 131688, 132967, 132967, 132967, 132967, 134250, 134250, 134260,
    134260, 134260, 134260, 135549, 135549, 136840, 136840, 136840, 136840,
    136840, 136840, 138137, 138137, 138137
]
N = int(read())
print(A[N])
0