#283725 (Python3) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	Min_25
提出日時	2018-09-08 12:12:32
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	200 ms / 3,000 ms
コード長	674 bytes
コンパイル時間	115 ms
コンパイル使用メモリ	10,780 KB
実行使用メモリ	89,384 KB
最終ジャッジ日時	2023-08-21 23:49:30
合計ジャッジ時間	17,512 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	129 ms 29,764 KB
testcase_01	AC	129 ms 29,808 KB
testcase_02	AC	129 ms 29,676 KB
testcase_03	AC	129 ms 29,768 KB
testcase_04	AC	129 ms 29,720 KB
testcase_05	AC	129 ms 29,796 KB
testcase_06	AC	128 ms 29,696 KB
testcase_07	AC	127 ms 29,788 KB
testcase_08	AC	130 ms 29,760 KB
testcase_09	AC	130 ms 29,764 KB
testcase_10	AC	131 ms 29,764 KB
testcase_11	AC	131 ms 29,744 KB
testcase_12	AC	130 ms 29,816 KB
testcase_13	AC	131 ms 29,724 KB
testcase_14	AC	131 ms 29,720 KB
testcase_15	AC	130 ms 29,624 KB
testcase_16	AC	131 ms 29,608 KB
testcase_17	AC	131 ms 29,788 KB
testcase_18	AC	132 ms 29,784 KB
testcase_19	AC	131 ms 29,728 KB
testcase_20	AC	130 ms 29,892 KB
testcase_21	AC	131 ms 30,276 KB
testcase_22	AC	132 ms 30,404 KB
testcase_23	AC	131 ms 29,852 KB
testcase_24	AC	131 ms 29,776 KB
testcase_25	AC	198 ms 31,796 KB
testcase_26	AC	137 ms 31,936 KB
testcase_27	AC	135 ms 30,224 KB
testcase_28	AC	134 ms 30,100 KB
testcase_29	AC	136 ms 30,304 KB
testcase_30	AC	137 ms 30,388 KB
testcase_31	AC	134 ms 30,284 KB
testcase_32	AC	134 ms 31,812 KB
testcase_33	AC	134 ms 31,972 KB
testcase_34	AC	135 ms 31,772 KB
testcase_35	AC	136 ms 31,812 KB
testcase_36	AC	135 ms 31,672 KB
testcase_37	AC	130 ms 29,968 KB
testcase_38	AC	132 ms 29,984 KB
testcase_39	AC	132 ms 31,724 KB
testcase_40	AC	131 ms 30,268 KB
testcase_41	AC	134 ms 30,512 KB
testcase_42	AC	133 ms 30,268 KB
testcase_43	AC	134 ms 30,204 KB
testcase_44	AC	134 ms 30,280 KB
testcase_45	AC	132 ms 30,148 KB
testcase_46	AC	131 ms 30,240 KB
testcase_47	AC	130 ms 30,276 KB
testcase_48	AC	132 ms 31,728 KB
testcase_49	AC	133 ms 31,736 KB
testcase_50	AC	130 ms 30,312 KB
testcase_51	AC	131 ms 30,176 KB
testcase_52	AC	132 ms 30,192 KB
testcase_53	AC	136 ms 33,552 KB
testcase_54	AC	166 ms 59,468 KB
testcase_55	AC	171 ms 61,016 KB
testcase_56	AC	168 ms 61,460 KB
testcase_57	AC	138 ms 37,380 KB
testcase_58	AC	140 ms 37,420 KB
testcase_59	AC	135 ms 33,556 KB
testcase_60	AC	151 ms 44,596 KB
testcase_61	AC	151 ms 44,604 KB
testcase_62	AC	170 ms 61,084 KB
testcase_63	AC	154 ms 45,024 KB
testcase_64	AC	152 ms 44,704 KB
testcase_65	AC	153 ms 44,700 KB
testcase_66	AC	129 ms 29,740 KB
testcase_67	AC	127 ms 29,800 KB
testcase_68	AC	165 ms 59,736 KB
testcase_69	AC	165 ms 59,800 KB
testcase_70	AC	167 ms 59,696 KB
testcase_71	AC	169 ms 59,784 KB
testcase_72	AC	152 ms 44,808 KB
testcase_73	AC	168 ms 61,180 KB
testcase_74	AC	169 ms 61,896 KB
testcase_75	AC	133 ms 31,800 KB
testcase_76	AC	171 ms 60,912 KB
testcase_77	AC	142 ms 37,456 KB
testcase_78	AC	166 ms 61,008 KB
testcase_79	AC	167 ms 59,308 KB
testcase_80	AC	169 ms 61,244 KB
testcase_81	AC	166 ms 61,200 KB
testcase_82	AC	128 ms 30,176 KB
testcase_83	AC	141 ms 37,448 KB
testcase_84	AC	147 ms 44,488 KB
testcase_85	AC	166 ms 59,588 KB
testcase_86	AC	168 ms 61,428 KB
testcase_87	AC	200 ms 89,200 KB
testcase_88	AC	198 ms 89,384 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
    s = 1 << (((n3 + 1) * 2 - 1).bit_length() - 1)
    v = int(n3 ** 0.5)
    isp = np.ones(n3 + 1, np.uint8)
    isp[0] = isp[1] = 0
    for i in range(2, v + 1):
      if isp[i]:
        isp[i*i::i] = 0
    f = np.zeros(s, np.complex128)
    f[:n+1] = isp[:n+1]
    p1 = fft(f)
    p2 = np.concatenate((p1[::2], p1[::2]))
    p3 = np.concatenate((p1[::3], p1[3-s%3::3], p1[s%3::3]))
    fg = (p1 * (p1 * p1 - 3.0 * p2) + 2.0 * p3) / 6.0
    g = ifft(fg).real.round().astype(np.int64)
    print(np.sum(g[np.nonzero(isp)]))

solve()

yukicoder

結果

テストケース

ソースコード