yukicoder - No.6

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

問題ページ

エラトステネスの篩で $N$ までの素数を列挙して，$[K, N]$ の範囲にある素数を配列にぶち込む．

ハッシュ値の取りうる種類を $H$ とすると $H = 10$ ( 1 桁の数の総数 ) なので，ハッシュが衝突しない最大の長さは高々 $H$ で抑えられる．
よって，尺取り法を書いて変なバグを埋め込むよりは，$[K, N]$ の各素数に対してハッシュが衝突しない最大の長さを求めていけばいい．

計算量は $n$ 以下の素数の個数を $\pi (n)$ として，

$O( \max \{ H( \pi(N) - \pi(K) ) , N \log \log N \} )$ とかになるので充分間に合う．

#include "bits/stdc++.h"

using namespace std;

int digitSum(int n) {
    while (n >= 10) {
        int m = 0;
        while (n) {
            m += n % 10;
            n /= 10;
        }
        n = m;
    }
    return n;
}

int hashLength(const vector<int>& primes, int left) {
    bool hash[10] = {};

    for (int right = left; right < primes.size(); right++) {
        int d = digitSum(primes[right]);

        if (hash[d]) return right - left;
        else hash[d] = true;
    }
    return primes.size() - left;
}

int main()
{
    const int MAX = 200010;
    vector<bool> p(MAX, true);
    p[0] = p[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if(p[i]) for (int j = i * i; j < MAX; j += i) {
            p[j] = false;
        }
    }

    int K, N;
    cin >> K >> N;

    vector<int> primes;
    for (int i = K; i <= N; i++) if (p[i]) primes.push_back(i);

    int maxLength = 0, ans;
    for (int i = 0; i < primes.size(); i++) {
        int length = hashLength(primes, i);
        if (maxLength <= length) {
            maxLength = length;
            ans = primes[i];
        }
    }

    cout << ans << endl;

    return 0;
}