結果
問題 | No.732 3PrimeCounting |
ユーザー | vwxyz |
提出日時 | 2022-10-03 02:39:15 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,290 bytes |
コンパイル時間 | 903 ms |
コンパイル使用メモリ | 87,168 KB |
実行使用メモリ | 101,120 KB |
最終ジャッジ日時 | 2023-08-26 23:54:46 |
合計ジャッジ時間 | 26,208 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 282 ms
96,056 KB |
testcase_01 | AC | 282 ms
96,344 KB |
testcase_02 | AC | 280 ms
96,144 KB |
testcase_03 | AC | 286 ms
96,332 KB |
testcase_04 | AC | 284 ms
96,056 KB |
testcase_05 | AC | 284 ms
96,100 KB |
testcase_06 | AC | 287 ms
96,180 KB |
testcase_07 | AC | 277 ms
96,128 KB |
testcase_08 | AC | 278 ms
95,940 KB |
testcase_09 | AC | 281 ms
96,372 KB |
testcase_10 | AC | 283 ms
96,368 KB |
testcase_11 | AC | 279 ms
95,968 KB |
testcase_12 | AC | 281 ms
96,312 KB |
testcase_13 | AC | 280 ms
96,368 KB |
testcase_14 | AC | 279 ms
95,968 KB |
testcase_15 | AC | 282 ms
96,096 KB |
testcase_16 | AC | 283 ms
95,944 KB |
testcase_17 | AC | 282 ms
95,912 KB |
testcase_18 | AC | 282 ms
95,924 KB |
testcase_19 | AC | 280 ms
96,012 KB |
testcase_20 | AC | 289 ms
97,528 KB |
testcase_21 | AC | 305 ms
97,756 KB |
testcase_22 | AC | 312 ms
97,760 KB |
testcase_23 | AC | 281 ms
97,108 KB |
testcase_24 | AC | 285 ms
97,260 KB |
testcase_25 | AC | 347 ms
98,380 KB |
testcase_26 | AC | 322 ms
98,004 KB |
testcase_27 | AC | 289 ms
97,320 KB |
testcase_28 | AC | 295 ms
97,404 KB |
testcase_29 | AC | 311 ms
97,728 KB |
testcase_30 | AC | 303 ms
98,084 KB |
testcase_31 | AC | 311 ms
97,768 KB |
testcase_32 | AC | 325 ms
98,064 KB |
testcase_33 | AC | 338 ms
98,472 KB |
testcase_34 | AC | 336 ms
98,316 KB |
testcase_35 | AC | 318 ms
97,804 KB |
testcase_36 | AC | 313 ms
97,800 KB |
testcase_37 | AC | 290 ms
97,288 KB |
testcase_38 | AC | 290 ms
97,296 KB |
testcase_39 | AC | 321 ms
98,060 KB |
testcase_40 | AC | 316 ms
97,968 KB |
testcase_41 | AC | 310 ms
97,968 KB |
testcase_42 | AC | 311 ms
97,792 KB |
testcase_43 | AC | 304 ms
98,128 KB |
testcase_44 | AC | 311 ms
98,008 KB |
testcase_45 | AC | 296 ms
97,504 KB |
testcase_46 | AC | 300 ms
97,412 KB |
testcase_47 | AC | 303 ms
97,648 KB |
testcase_48 | AC | 354 ms
98,920 KB |
testcase_49 | AC | 349 ms
98,720 KB |
testcase_50 | AC | 311 ms
98,008 KB |
testcase_51 | AC | 306 ms
98,076 KB |
testcase_52 | AC | 293 ms
97,352 KB |
testcase_53 | AC | 479 ms
101,120 KB |
testcase_54 | TLE | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
testcase_57 | -- | - |
testcase_58 | -- | - |
testcase_59 | -- | - |
testcase_60 | -- | - |
testcase_61 | -- | - |
testcase_62 | -- | - |
testcase_63 | -- | - |
testcase_64 | -- | - |
testcase_65 | -- | - |
testcase_66 | -- | - |
testcase_67 | -- | - |
testcase_68 | -- | - |
testcase_69 | -- | - |
testcase_70 | -- | - |
testcase_71 | -- | - |
testcase_72 | -- | - |
testcase_73 | -- | - |
testcase_74 | -- | - |
testcase_75 | -- | - |
testcase_76 | -- | - |
testcase_77 | -- | - |
testcase_78 | -- | - |
testcase_79 | -- | - |
testcase_80 | -- | - |
testcase_81 | -- | - |
testcase_82 | -- | - |
testcase_83 | -- | - |
testcase_84 | -- | - |
testcase_85 | -- | - |
testcase_86 | -- | - |
testcase_87 | -- | - |
testcase_88 | -- | - |
ソースコード
from ast import Mod import bisect import copy import decimal import fractions import heapq import itertools import math import random import sys import time from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines write=sys.stdout.write class Prime: def __init__(self,N): assert N<=10**8 self.smallest_prime_factor=[None]*(N+1) for i in range(2,N+1,2): self.smallest_prime_factor[i]=2 n=int(N**.5)+1 for p in range(3,n,2): if self.smallest_prime_factor[p]==None: self.smallest_prime_factor[p]=p for i in range(p**2,N+1,2*p): if self.smallest_prime_factor[i]==None: self.smallest_prime_factor[i]=p for p in range(n,N+1): if self.smallest_prime_factor[p]==None: self.smallest_prime_factor[p]=p self.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]] def Factorize(self,N): assert N>=1 factors=defaultdict(int) if N<=len(self.smallest_prime_factor)-1: while N!=1: factors[self.smallest_prime_factor[N]]+=1 N//=self.smallest_prime_factor[N] else: for p in self.primes: while N%p==0: N//=p factors[p]+=1 if N<p*p: if N!=1: factors[N]+=1 break if N<=len(self.smallest_prime_factor)-1: while N!=1: factors[self.smallest_prime_factor[N]]+=1 N//=self.smallest_prime_factor[N] break else: if N!=1: factors[N]+=1 return factors def Divisors(self,N): assert N>0 divisors=[1] for p,e in self.Factorize(N).items(): pow_p=[1] for _ in range(e): pow_p.append(pow_p[-1]*p) divisors=[i*j for i in divisors for j in pow_p] return divisors def Is_Prime(self,N): return N==self.smallest_prime_factor[N] def Totient(self,N): for p in self.Factorize(N).keys(): N*=p-1 N//=p return N def Mebius(self,N): fact=self.Factorize(N) for e in fact.values(): if e>=2: return 0 else: if len(fact)%2==0: return 1 else: return -1 N=int(readline()) P=Prime(3*N) primes=[p for p in P.primes if p<=N] cnt=defaultdict(int) le=len(primes) ans=0 for b in range(le-1,-1,-1): for a in range(b-1,-1,-1): ans+=cnt[primes[a]+primes[b]] for p in P.primes: cnt[p-primes[b]]+=1 print(ans)