結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
|
提出日時 | 2020-04-04 16:25:14 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,416 bytes |
コンパイル時間 | 2,385 ms |
コンパイル使用メモリ | 79,864 KB |
実行使用メモリ | 58,600 KB |
最終ジャッジ日時 | 2024-07-03 07:27:27 |
合計ジャッジ時間 | 71,992 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 87 TLE * 2 |
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { long curtime=System.currentTimeMillis(); new Main().run(); System.err.println(System.currentTimeMillis()-curtime); } int MAX=300001; boolean[] isPrime=new boolean[MAX]; ArrayList<Integer> primes=new ArrayList<>(); { Arrays.fill(isPrime, true); isPrime[0]=isPrime[1]=false; for(int i=2;i<isPrime.length;++i) { if(!isPrime[i])continue; primes.add(i); for(int j=2*i;j<isPrime.length;j+=i) isPrime[j]=false; } } void run() { Scanner sc=new Scanner(System.in); int N=sc.nextInt();//5<=N<=1e5 long[] dp=new long[MAX]; for(int p:primes) { if(p>N)break; for(int q:primes) { if(q>N)break; ++dp[p+q]; } } long ans=0; int src=0; for(int p:primes) { if(p>N)break; while(src<primes.size()&&primes.get(src)-p<=0)++src; for(int i=src;i<primes.size();++i) { int target=primes.get(i); if(target-p<=0)continue; ans+=dp[target-p]; } } //a+b+c が 素数 かつ a==b==c は存在しない。 for(int p:primes) { if(p>N)break; for(int q:primes) { if(q>N)break; if(isPrime[p+p+q]) { ans-=3; } } } if(ans%6!=0)throw new AssertionError(); System.out.println(ans/6); } void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} }