Mister雑記

競プロやります。

TCO2019 Round3B Medium 「PrefixComposite」(450)

community.topcoder.com

問題

約数を3つ以上持つ( \iff1でも素数でもない)正整数を合成数という。

また、10進数表記したときに全ての接頭辞が合成数であるような正整数を接尾合成数と呼ぶことにする。

正整数 A, Bが与えられる。区間 [A, B]に接尾合成数が存在するか判定し、存在すればその中で最小、最大のものをそれぞれ求めよ。

制約

  •  1 \leq A, B \leq 10^{11}

考察

 A以上で最小、 B以下で最大の接尾合成数をそれぞれ求めれば、その大小で区間内に接尾合成数が存在するかが分かる。

 A以上で最小の接尾合成数を求めることを考える。  A = 10P + Q (0 \leq Q \leq 9)とおき、 P以上の最小の接尾合成数 P'とする。これは再帰的に求まる。

 P' \gt Pならば、 10P'以上で最小の合成数が解となる。これは 10P'から素数判定しつつインクリメントしていけばいい1

そうでない場合は、 Aから合成数になるまでインクリメントしていけばいい。ただし Q = 9の場合が危険で、 A素数であった場合はインクリメントによって Pの値が変わってしまう。この場合はまた最初に戻ってやるとよい。

 B以下で最大の接尾合成数もほとんど同じようにして求まる。2以外の偶数が合成数であることから各インクリメント・デクリメントは高々1回で終わるので、計算量は \sqrt{B} \log B程度になるはず(素数判定と桁数)。

実装例

using namespace std;
using lint = long long;

bool isprime(lint n) {
    if (n == 0) return false;
    for (lint i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

class PrefixComposite {
    lint small(lint X) {
        if (X == 0) return X;

        while (true) {
            lint P = X / 10;
            lint NP = small(P);
            if (NP < P) X = NP * 10 + 9;

            while (isprime(X)) --X;
            if (P == X / 10) break;
        }
        return X;
    }

    lint big(lint X) {
        if (X == 0) return X;

        while (true) {
            lint P = X / 10;
            lint NP = big(P);
            if (NP > P) X = NP * 10;

            while (isprime(X)) ++X;
            if (P == X / 10) break;
        }
        return X;
    }

public:
    vector<lint> minMax(lint A, lint B) {
        lint R = small(B);
        lint L = big(A);
        if (L > R) {
            return vector<lint>(0);
        } else {
            return vector<lint>({L, R});
        }
    }
};

反省

  • 順当に考察が進められた。
  •  Pが変わるコーナーケースはサンプルに救われた。

  1.  10P'は10の倍数なので必ず合成数なのだが、最大の場合との対称性を意識してこの書き方をしている。