結果
問題 | No.732 3PrimeCounting |
ユーザー |
![]() |
提出日時 | 2018-09-20 12:25:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 639 ms / 3,000 ms |
コード長 | 1,039 bytes |
コンパイル時間 | 786 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-07-18 08:31:40 |
合計ジャッジ時間 | 8,098 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> using namespace std; typedef long long int ll; typedef pair<int, int> P; int n; vector<int> prime; bool isprime[300001]; void sieve(){ for(int i=3; i<=3*n; i+=2){ isprime[i]=1; } isprime[2]=1; prime.push_back(2); for(int i=3; i<=3*n; i++){ if(isprime[i]){ prime.push_back(i); for(int j=2*i; j<=3*n; j+=i){ isprime[j]=0; } } } return; } int main() { cin>>n; sieve(); ll ct1[200001]={}, ct2[200001]={}, ct3=0; for(int i=0; prime[i]<=n; i++){ for(int j=0; prime[j]<=n; j++){ ct1[prime[i]+prime[j]]++; if(isprime[2*prime[i]+prime[j]]) ct3+=3; } } for(int i=0; prime[i]<=n; i++){ for(int j=i+1; (j<prime.size() && prime[j]-prime[i]<=2*n); j++){ ct2[prime[j]-prime[i]]++; } } ll ans=0; for(int i=1; i<=2*n; i++){ ans+=ct1[i]*ct2[i]; } cout<<(ans-ct3)/6<<endl; return 0; }