結果

問題 No.732 3PrimeCounting
ユーザー rpy3cpp
提出日時 2019-05-16 18:07:52
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 1,387 ms
コード長 1,260 Byte
コンパイル時間 1,323 ms
使用メモリ 8,920 KB
最終ジャッジ日時 2019-09-21 08:08:08

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 5 ms
6,876 KB
case2.txt AC 3 ms
6,872 KB
case3.txt AC 3 ms
8,920 KB
case4.txt AC 4 ms
6,876 KB
case5.txt AC 2 ms
6,876 KB
case6.txt AC 4 ms
6,872 KB
case7.txt AC 4 ms
6,876 KB
case8.txt AC 3 ms
6,876 KB
case9.txt AC 3 ms
6,872 KB
case10.txt AC 2 ms
8,920 KB
case11.txt AC 2 ms
6,876 KB
case12.txt AC 4 ms
6,876 KB
case13.txt AC 2 ms
8,920 KB
case14.txt AC 3 ms
6,876 KB
case15.txt AC 2 ms
6,876 KB
case16.txt AC 3 ms
6,872 KB
case17.txt AC 2 ms
6,872 KB
case18.txt AC 2 ms
6,872 KB
case19.txt AC 3 ms
6,876 KB
case20.txt AC 3 ms
6,876 KB
case21.txt AC 3 ms
6,876 KB
case22.txt AC 5 ms
6,876 KB
case23.txt AC 5 ms
6,872 KB
case24.txt AC 3 ms
6,872 KB
case25.txt AC 3 ms
6,876 KB
case26.txt AC 8 ms
6,872 KB
case27.txt AC 6 ms
6,876 KB
case28.txt AC 3 ms
6,872 KB
case29.txt AC 4 ms
6,876 KB
case30.txt AC 4 ms
6,876 KB
case31.txt AC 4 ms
6,876 KB
case32.txt AC 5 ms
6,872 KB
case33.txt AC 6 ms
6,872 KB
case34.txt AC 7 ms
6,872 KB
case35.txt AC 6 ms
6,876 KB
case36.txt AC 5 ms
6,876 KB
case37.txt AC 6 ms
6,872 KB
case38.txt AC 3 ms
6,872 KB
case39.txt AC 3 ms
6,876 KB
case40.txt AC 6 ms
6,872 KB
case41.txt AC 5 ms
6,876 KB
case42.txt AC 5 ms
8,920 KB
case43.txt AC 6 ms
6,876 KB
case44.txt AC 5 ms
6,876 KB
case45.txt AC 4 ms
6,872 KB
case46.txt AC 4 ms
6,876 KB
case47.txt AC 4 ms
6,872 KB
case48.txt AC 4 ms
8,912 KB
case49.txt AC 8 ms
6,872 KB
case50.txt AC 9 ms
6,876 KB
case51.txt AC 5 ms
6,872 KB
case52.txt AC 5 ms
6,876 KB
case53.txt AC 3 ms
6,876 KB
case54.txt AC 22 ms
6,872 KB
case55.txt AC 451 ms
6,872 KB
case56.txt AC 444 ms
8,916 KB
case57.txt AC 448 ms
6,872 KB
case58.txt AC 71 ms
6,872 KB
case59.txt AC 71 ms
6,876 KB
case60.txt AC 23 ms
6,872 KB
case61.txt AC 115 ms
6,876 KB
case62.txt AC 113 ms
6,876 KB
case63.txt AC 599 ms
6,876 KB
case64.txt AC 233 ms
6,876 KB
case65.txt AC 157 ms
6,876 KB
case66.txt AC 156 ms
6,876 KB
case67.txt AC 3 ms
6,876 KB
case68.txt AC 3 ms
6,876 KB
case69.txt AC 517 ms
6,872 KB
case70.txt AC 517 ms
6,876 KB
case71.txt AC 452 ms
6,876 KB
case72.txt AC 464 ms
6,872 KB
case73.txt AC 220 ms
6,872 KB
case74.txt AC 1,014 ms
6,872 KB
case75.txt AC 1,005 ms
6,872 KB
case76.txt AC 7 ms
6,872 KB
case77.txt AC 500 ms
6,876 KB
case78.txt AC 77 ms
8,920 KB
case79.txt AC 764 ms
6,872 KB
case80.txt AC 520 ms
6,876 KB
case81.txt AC 681 ms
6,876 KB
case82.txt AC 457 ms
6,876 KB
case83.txt AC 3 ms
6,876 KB
case84.txt AC 72 ms
6,876 KB
case85.txt AC 85 ms
6,876 KB
case86.txt AC 379 ms
6,872 KB
case87.txt AC 690 ms
6,876 KB
case88.txt AC 1,387 ms
6,876 KB
case89.txt AC 1,387 ms
6,872 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>
using namespace std;

vector<int> primes2(int N){
    // returns a list of prime numbers up to N (including N).
    if (N == 1) return vector<int>{};
    if (N == 2) return vector<int>{2};
    if (N <= 4) return vector<int>{2, 3};
    vector<bool> isPrime(N + 1, true);
    for (int p = 5, d = 2; p * p <= N; p += d, d = 6 - d){
        if (isPrime[p]){
            for (int q = p * p, delta = d; q <= N; q += delta * p, delta = 6 - delta){
                isPrime[q] = false;
            }
        }
    }
    vector<int> primes = {2, 3};
    for (int p = 5, d = 2; p <= N; p += d, d = 6 - d){
        if (isPrime[p]) primes.push_back(p);
    }
    return primes;
}

int main(){
    int N;
    cin >> N;
    vector<int> ps = primes2(3 * N);
    vector<int> ds((3 * N)/2 + 1, 0);
    for (auto p : ps) ds[p/2] = 1;
    vector<int> hps;
    for (int i = 1; ps[i] <= N; ++i){
        hps.push_back(ps[i]/2);
    }
    vector<long long> ab(N, 0);
    long long cnt = 0;
    for (int i = 1; i < hps.size(); ++i){
        for (int j = 1; j < hps[i] * 2; ++j){
            if (ab[j] and ds[j + hps[i] + 1]) cnt += ab[j];
        }
        for (int j = 0; j < i; ++j) ab[hps[j] + hps[i]] += 1LL;
    }
    cout << cnt << endl;
    return 0;
}
0