#660483 (Python3) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	shotoyoo
提出日時	2021-05-26 00:21:34
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	771 ms / 3,000 ms
コード長	1,505 bytes
コンパイル時間	87 ms
コンパイル使用メモリ	12,800 KB
実行使用メモリ	83,172 KB
最終ジャッジ日時	2024-04-22 16:03:57
合計ジャッジ時間	53,177 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	487 ms 44,324 KB
testcase_01	AC	485 ms 44,588 KB
testcase_02	AC	483 ms 44,580 KB
testcase_03	AC	487 ms 44,204 KB
testcase_04	AC	486 ms 44,204 KB
testcase_05	AC	483 ms 44,200 KB
testcase_06	AC	487 ms 44,200 KB
testcase_07	AC	494 ms 44,584 KB
testcase_08	AC	482 ms 44,580 KB
testcase_09	AC	491 ms 44,308 KB
testcase_10	AC	484 ms 44,452 KB
testcase_11	AC	493 ms 44,200 KB
testcase_12	AC	490 ms 44,576 KB
testcase_13	AC	494 ms 44,460 KB
testcase_14	AC	479 ms 44,584 KB
testcase_15	AC	483 ms 44,456 KB
testcase_16	AC	485 ms 44,456 KB
testcase_17	AC	480 ms 44,204 KB
testcase_18	AC	489 ms 44,200 KB
testcase_19	AC	492 ms 44,580 KB
testcase_20	AC	481 ms 44,456 KB
testcase_21	AC	496 ms 44,832 KB
testcase_22	AC	482 ms 44,836 KB
testcase_23	AC	489 ms 44,204 KB
testcase_24	AC	476 ms 44,208 KB
testcase_25	AC	493 ms 44,200 KB
testcase_26	AC	500 ms 44,584 KB
testcase_27	AC	498 ms 44,204 KB
testcase_28	AC	496 ms 44,584 KB
testcase_29	AC	503 ms 44,460 KB
testcase_30	AC	485 ms 44,720 KB
testcase_31	AC	496 ms 44,204 KB
testcase_32	AC	490 ms 44,712 KB
testcase_33	AC	502 ms 44,072 KB
testcase_34	AC	494 ms 44,236 KB
testcase_35	AC	502 ms 44,200 KB
testcase_36	AC	486 ms 44,200 KB
testcase_37	AC	489 ms 44,200 KB
testcase_38	AC	488 ms 44,196 KB
testcase_39	AC	506 ms 44,592 KB
testcase_40	AC	491 ms 44,072 KB
testcase_41	AC	498 ms 44,584 KB
testcase_42	AC	498 ms 44,716 KB
testcase_43	AC	507 ms 44,464 KB
testcase_44	AC	484 ms 44,452 KB
testcase_45	AC	488 ms 44,200 KB
testcase_46	AC	485 ms 44,328 KB
testcase_47	AC	493 ms 44,460 KB
testcase_48	AC	498 ms 44,204 KB
testcase_49	AC	499 ms 44,208 KB
testcase_50	AC	486 ms 44,576 KB
testcase_51	AC	493 ms 44,584 KB
testcase_52	AC	486 ms 44,464 KB
testcase_53	AC	595 ms 44,980 KB
testcase_54	AC	646 ms 62,572 KB
testcase_55	AC	634 ms 62,460 KB
testcase_56	AC	634 ms 62,544 KB
testcase_57	AC	539 ms 46,360 KB
testcase_58	AC	532 ms 46,488 KB
testcase_59	AC	516 ms 44,968 KB
testcase_60	AC	556 ms 51,888 KB
testcase_61	AC	556 ms 51,604 KB
testcase_62	AC	655 ms 64,116 KB
testcase_63	AC	594 ms 53,028 KB
testcase_64	AC	567 ms 52,372 KB
testcase_65	AC	573 ms 51,992 KB
testcase_66	AC	498 ms 44,200 KB
testcase_67	AC	486 ms 44,204 KB
testcase_68	AC	652 ms 63,728 KB
testcase_69	AC	664 ms 63,080 KB
testcase_70	AC	646 ms 62,480 KB
testcase_71	AC	646 ms 62,220 KB
testcase_72	AC	584 ms 52,636 KB
testcase_73	AC	711 ms 66,068 KB
testcase_74	AC	705 ms 65,544 KB
testcase_75	AC	501 ms 44,204 KB
testcase_76	AC	647 ms 63,048 KB
testcase_77	AC	548 ms 46,236 KB
testcase_78	AC	674 ms 65,532 KB
testcase_79	AC	641 ms 63,468 KB
testcase_80	AC	686 ms 65,028 KB
testcase_81	AC	662 ms 62,624 KB
testcase_82	AC	498 ms 44,200 KB
testcase_83	AC	536 ms 46,744 KB
testcase_84	AC	544 ms 49,956 KB
testcase_85	AC	645 ms 62,264 KB
testcase_86	AC	672 ms 65,316 KB
testcase_87	AC	765 ms 82,932 KB
testcase_88	AC	771 ms 83,172 KB

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

ソースコード

raw source code

import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))

def hurui(n):
    """線形篩
    pl: 素数のリスト
    mpf: iを割り切る最小の素因数
    """
    pl = []
    mpf = [None]*(n+1)
    for d in range(2,n+1):
        if mpf[d] is None:
            mpf[d] = d
            pl.append(d)
        for p in pl:
            if p*d>n or p>mpf[d]:
                break
            mpf[p*d] = p
    return pl, mpf
# FFT
import numpy as np
TYPE = np.int32
M = 998244353
def fft(a,b):
    l = len(a) + len(b) - 1
    l = 1<<((l-1).bit_length())
    a = np.array(a)
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(TYPE)
    s = np.where(c>0)[0].max()
    return c[:s+1]
def fft_large(a,b):
    d = 30000
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
n = int(input())
pl, _ = hurui(3*n)
ps = [v for v in pl if v<=n]
ok = [0]*(n+1)
ok2 = [0]*(2*n+1)
for p in ps:
    ok[p] = 1
    ok2[2*p] = 1
mask = [0]*(3*n+1)
for p in pl:
    mask[p] = 1
b2 = fft(ok, ok)
b3 = fft(b2, ok)
b22 = fft(ok, ok2)
mask = np.array(mask, dtype=bool)
val1 = b3[mask[:b3.shape[0]]].sum()
val2 = b22[mask[:b22.shape[0]]].sum()
ans = (val1-val2*3)//6
print(ans)

yukicoder

結果

テストケース

ソースコード