yukicoder No.6 使いものにならないハッシュ

No.6 使いものにならないハッシュ - yukicoder

問題概要

で素数の連続部分列のうち、桁和ハッシュ( 桁になるまで行う)が衝突しない最大のものを求めよ。

解法

しゃくとり実装面倒だったのでズルをした。素数の個数が対数オーダー、かつハッシュがたかだか 種類だったので全探索で余裕で通る。

vector<ll> prime(ll n) {
    vector<ll> Prime(n + 1);
    rep(i, n + 1) Prime[i] = 1;
    Prime[0] = Prime[1] = 0;
    rep(i, n + 1) {
        if (Prime[i]) {
            rep(j, n / i - 1) Prime[i * (j + 2)] = 0;
        }
    }
    return Prime;
}

ll Hash(ll n) {
    if (n < 10) return n;
    ll S = 0;
    while (n) S += n % 10, n /= 10;
    return Hash(S);
}

int main() {
    ll N, K;
    cin >> K >> N;
    vector<ll> P = prime(N), Q;
    inc(i, K, N) if (P[i]) Q.pb(i);
    ll res, max = 0;
    rep(i, Q.size()) {
        map<ll, ll> M;
        rep(j, Q.size() - i) {
            if (M[Hash(Q[i + j])]++) {
                if (max <= j) {
                    max = j;
                    res = Q[i];
                }
                goto end;
            }
        }
        if (max <= Q.size() - i) {
            max = Q.size() - i;
            res = Q[i];
        }
    end:;
    }
    cout << res << endl;
}