No.732 3PrimeCounting

問題

以下の相異なる3つの素数の組のうち、が素数になるものはいくつあるか。

No.732 3PrimeCounting - yukicoder

解法

100000以下の素数の個数は10000個ぐらいなので、で間に合う。ただしは以下の素数の個数。この問題の場合、自明な解が10分ぐらい待てば動くので、答えを埋め込むのも手ですが、ここでは正攻法を解説します。

triplet系の問題は一つ固定して考えるのがあまりに定石ですが、今回はとを固定します。このとき、より小さい素数の組で和がhogeになるものが何通りあるかを、あらゆるhogeについてすぐに答えられるといいです。

これを求めるのには、（に関するforループ内で）に関する2重ループを回して可能な和をすべて調べればできますが、合わせて3重ループになるのでTLEしてしまいます。しかし、数え上げに注目すると、が次のものに変わるとき、ひとつ前に数えたものはすべて重複して数えられています。が次のものに変わるとき、新しくカウントされる組み合わせはとなっているものに限られることに注目すると、オーダーが一つ落ち、間に合います。

実装

エラトステネスの篩の部分は省略しています。

bool is_prime[303030];
int cnt[303030];
vi primes;

int main() {
    init();
    int n;
    cin >> n;
    i64 ans = 0;
    for (int i = 1; i < primes.size(); i++) {
        int c = primes[i];
        if (c > n) break;
        int b = primes[i - 1];
        for (int j = 0; j < i - 1; j++) {
            int a = primes[j];
            cnt[a + b]++;
        }
        for (int j = 0; j < primes.size(); j++) {
            int sum = primes[j];
            if (sum - c >= 0) {
                ans += cnt[sum - c];
            }
        }
    }
    cout << ans << endl;
}

感想

大小関係があるtripletの数え上げは、今回のように一番大きいものを固定すると差分だけを数えられるようになってオーダーが落ちますね。典型か？