結果

問題 No.732 3PrimeCounting
ユーザー shotoyooshotoyoo
提出日時 2021-05-26 00:21:08
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,505 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 81,876 KB
実行使用メモリ 67,144 KB
最終ジャッジ日時 2024-10-14 15:09:46
合計ジャッジ時間 8,239 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 89
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0