結果

問題 No.732 3PrimeCounting
コンテスト
ユーザー Min_25
提出日時 2018-09-08 11:54:37
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,292 ms / 3,000 ms
コード長 761 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 87,700 KB
最終ジャッジ日時 2024-12-15 07:54:37
合計ジャッジ時間 60,986 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 89
権限があれば一括ダウンロードができます

ソースコード

diff # 

import numpy as np

def solve():
  from sys import stdin
  from numpy.fft import fft, ifft
  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]
    ff, fg = fft(f), np.zeros(s, np.complex128)
    mask = s - 1
    for i in range(s):
      p1, p2, p3 = ff[i], ff[(2 * i) & mask], ff[(3 * i) & mask]
      e1 = p1
      e2 = (e1 * p1 - p2) / 2.0
      e3 = (e2 * p1 - e1 * p2 + p3) / 3.0
      fg[i] = e3
    g = ifft(fg).real.round().astype(np.int64)
    print(np.sum(g[np.nonzero(isp)]))

solve()
0