#283724 (Python3) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	Min_25
提出日時	2018-09-08 12:06:08
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	213 ms / 3,000 ms
コード長	722 bytes
コンパイル時間	117 ms
コンパイル使用メモリ	10,952 KB
実行使用メモリ	99,084 KB
最終ジャッジ日時	2023-08-21 21:50:54
合計ジャッジ時間	19,059 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	131 ms 29,724 KB
testcase_01	AC	132 ms 29,732 KB
testcase_02	AC	132 ms 29,724 KB
testcase_03	AC	130 ms 29,836 KB
testcase_04	AC	130 ms 29,728 KB
testcase_05	AC	130 ms 29,684 KB
testcase_06	AC	131 ms 29,684 KB
testcase_07	AC	130 ms 29,708 KB
testcase_08	AC	130 ms 29,744 KB
testcase_09	AC	132 ms 29,744 KB
testcase_10	AC	131 ms 29,692 KB
testcase_11	AC	130 ms 29,796 KB
testcase_12	AC	130 ms 29,764 KB
testcase_13	AC	129 ms 29,704 KB
testcase_14	AC	131 ms 29,804 KB
testcase_15	AC	132 ms 29,748 KB
testcase_16	AC	133 ms 29,712 KB
testcase_17	AC	134 ms 29,740 KB
testcase_18	AC	133 ms 29,704 KB
testcase_19	AC	131 ms 29,724 KB
testcase_20	AC	132 ms 30,032 KB
testcase_21	AC	134 ms 30,552 KB
testcase_22	AC	131 ms 30,488 KB
testcase_23	AC	130 ms 29,800 KB
testcase_24	AC	132 ms 29,872 KB
testcase_25	AC	150 ms 32,216 KB
testcase_26	AC	134 ms 32,120 KB
testcase_27	AC	132 ms 30,380 KB
testcase_28	AC	132 ms 30,236 KB
testcase_29	AC	132 ms 30,484 KB
testcase_30	AC	132 ms 30,504 KB
testcase_31	AC	134 ms 30,516 KB
testcase_32	AC	133 ms 32,004 KB
testcase_33	AC	133 ms 32,056 KB
testcase_34	AC	136 ms 32,060 KB
testcase_35	AC	133 ms 32,172 KB
testcase_36	AC	134 ms 32,052 KB
testcase_37	AC	130 ms 29,980 KB
testcase_38	AC	131 ms 29,968 KB
testcase_39	AC	135 ms 32,016 KB
testcase_40	AC	132 ms 30,620 KB
testcase_41	AC	132 ms 30,476 KB
testcase_42	AC	134 ms 30,728 KB
testcase_43	AC	131 ms 30,488 KB
testcase_44	AC	131 ms 30,484 KB
testcase_45	AC	131 ms 30,320 KB
testcase_46	AC	131 ms 30,292 KB
testcase_47	AC	133 ms 30,528 KB
testcase_48	AC	134 ms 32,032 KB
testcase_49	AC	132 ms 31,996 KB
testcase_50	AC	130 ms 30,556 KB
testcase_51	AC	132 ms 30,536 KB
testcase_52	AC	130 ms 30,252 KB
testcase_53	AC	137 ms 34,180 KB
testcase_54	AC	173 ms 63,716 KB
testcase_55	AC	173 ms 65,664 KB
testcase_56	AC	175 ms 63,592 KB
testcase_57	AC	143 ms 38,676 KB
testcase_58	AC	143 ms 38,480 KB
testcase_59	AC	138 ms 34,096 KB
testcase_60	AC	157 ms 46,932 KB
testcase_61	AC	156 ms 46,788 KB
testcase_62	AC	177 ms 63,784 KB
testcase_63	AC	157 ms 46,904 KB
testcase_64	AC	158 ms 46,788 KB
testcase_65	AC	158 ms 46,892 KB
testcase_66	AC	132 ms 29,872 KB
testcase_67	AC	135 ms 29,792 KB
testcase_68	AC	179 ms 63,648 KB
testcase_69	AC	179 ms 65,532 KB
testcase_70	AC	176 ms 63,472 KB
testcase_71	AC	175 ms 63,580 KB
testcase_72	AC	155 ms 46,940 KB
testcase_73	AC	175 ms 64,376 KB
testcase_74	AC	173 ms 64,108 KB
testcase_75	AC	136 ms 32,008 KB
testcase_76	AC	174 ms 63,664 KB
testcase_77	AC	143 ms 38,476 KB
testcase_78	AC	174 ms 64,036 KB
testcase_79	AC	174 ms 63,784 KB
testcase_80	AC	174 ms 63,828 KB
testcase_81	AC	175 ms 63,612 KB
testcase_82	AC	130 ms 30,172 KB
testcase_83	AC	142 ms 38,488 KB
testcase_84	AC	156 ms 46,660 KB
testcase_85	AC	174 ms 63,728 KB
testcase_86	AC	173 ms 63,748 KB
testcase_87	AC	213 ms 99,084 KB
testcase_88	AC	211 ms 97,436 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import numpy as np
from numpy.fft import fft, ifft
from sys import stdin

def solve():
  for line in stdin:
    n = int(line)
    n3 = n * 3
    isp = np.ones(n3 + 1, np.uint8)
    v = int(n3 ** 0.5)
    for i in range(2, v + 1):
      if isp[i]:
        isp[i*i::i] = 0
    isp[0] = isp[1] = 0
    s = 1 << (((n3 + 1) * 2 - 1).bit_length() - 1)
    f = np.zeros(s, np.complex128)
    f[:n+1] = isp[:n+1]
    p1, fg = fft(f), np.zeros(s, np.complex128)
    p2 = np.concatenate((p1[::2], p1[::2]))
    p3 = np.concatenate((p1[::3], p1[3-s%3::3], p1[s%3::3]))
    e2 = (p1 * p1 - p2) / 2.0
    fg = (e2 * p1 - p1 * p2 + p3) / 3.0
    g = ifft(fg).real.round().astype(np.int64)
    print(np.sum(g[np.nonzero(isp)]))

solve()

yukicoder

結果

テストケース

ソースコード