結果

問題 No.732 3PrimeCounting
ユーザー rpy3cpp
提出日時 2019-05-16 18:07:52
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 1,324 ms
コード長 1,260 Byte
コンパイル時間 1,368 ms
使用メモリ 4,556 KB
最終ジャッジ日時 2020-01-31 04:01:37

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 0 ms
3,280 KB
case2.txt AC 0 ms
3,276 KB
case3.txt AC 4 ms
3,360 KB
case4.txt AC 4 ms
3,216 KB
case5.txt AC 0 ms
3,368 KB
case6.txt AC 0 ms
3,348 KB
case7.txt AC 4 ms
3,288 KB
case8.txt AC 4 ms
3,268 KB
case9.txt AC 0 ms
3,412 KB
case10.txt AC 0 ms
3,244 KB
case11.txt AC 0 ms
3,252 KB
case12.txt AC 4 ms
3,216 KB
case13.txt AC 0 ms
3,352 KB
case14.txt AC 0 ms
3,352 KB
case15.txt AC 4 ms
3,352 KB
case16.txt AC 4 ms
3,252 KB
case17.txt AC 4 ms
3,252 KB
case18.txt AC 4 ms
3,408 KB
case19.txt AC 0 ms
3,244 KB
case20.txt AC 0 ms
3,272 KB
case21.txt AC 4 ms
3,364 KB
case22.txt AC 4 ms
3,412 KB
case23.txt AC 4 ms
3,312 KB
case24.txt AC 4 ms
3,256 KB
case25.txt AC 0 ms
3,360 KB
case26.txt AC 4 ms
3,436 KB
case27.txt AC 4 ms
3,336 KB
case28.txt AC 0 ms
3,280 KB
case29.txt AC 0 ms
3,232 KB
case30.txt AC 4 ms
3,268 KB
case31.txt AC 0 ms
3,308 KB
case32.txt AC 4 ms
3,400 KB
case33.txt AC 4 ms
3,352 KB
case34.txt AC 4 ms
3,336 KB
case35.txt AC 4 ms
3,476 KB
case36.txt AC 0 ms
3,348 KB
case37.txt AC 4 ms
3,348 KB
case38.txt AC 0 ms
3,224 KB
case39.txt AC 0 ms
3,368 KB
case40.txt AC 4 ms
3,468 KB
case41.txt AC 0 ms
3,396 KB
case42.txt AC 4 ms
3,404 KB
case43.txt AC 0 ms
3,416 KB
case44.txt AC 4 ms
3,248 KB
case45.txt AC 0 ms
3,392 KB
case46.txt AC 4 ms
3,224 KB
case47.txt AC 4 ms
3,388 KB
case48.txt AC 0 ms
3,380 KB
case49.txt AC 4 ms
3,372 KB
case50.txt AC 4 ms
3,372 KB
case51.txt AC 4 ms
3,292 KB
case52.txt AC 4 ms
3,336 KB
case53.txt AC 0 ms
3,300 KB
case54.txt AC 16 ms
3,336 KB
case55.txt AC 412 ms
3,620 KB
case56.txt AC 412 ms
3,608 KB
case57.txt AC 416 ms
3,608 KB
case58.txt AC 64 ms
3,392 KB
case59.txt AC 64 ms
3,356 KB
case60.txt AC 16 ms
3,532 KB
case61.txt AC 100 ms
3,404 KB
case62.txt AC 104 ms
3,404 KB
case63.txt AC 556 ms
3,952 KB
case64.txt AC 216 ms
3,768 KB
case65.txt AC 144 ms
3,348 KB
case66.txt AC 140 ms
3,344 KB
case67.txt AC 0 ms
3,272 KB
case68.txt AC 4 ms
3,224 KB
case69.txt AC 476 ms
3,880 KB
case70.txt AC 476 ms
3,896 KB
case71.txt AC 420 ms
3,764 KB
case72.txt AC 420 ms
3,648 KB
case73.txt AC 196 ms
3,408 KB
case74.txt AC 936 ms
4,204 KB
case75.txt AC 932 ms
4,200 KB
case76.txt AC 4 ms
3,288 KB
case77.txt AC 464 ms
3,912 KB
case78.txt AC 68 ms
3,484 KB
case79.txt AC 716 ms
4,160 KB
case80.txt AC 484 ms
4,004 KB
case81.txt AC 628 ms
4,004 KB
case82.txt AC 428 ms
3,752 KB
case83.txt AC 0 ms
3,292 KB
case84.txt AC 68 ms
3,600 KB
case85.txt AC 76 ms
3,472 KB
case86.txt AC 352 ms
3,740 KB
case87.txt AC 644 ms
4,204 KB
case88.txt AC 1,324 ms
4,444 KB
case89.txt AC 1,324 ms
4,556 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