Yukicoder006 使いものにならないハッシュ

問題概要

$hash$を、整数の桁の和について、1桁になるまで再帰的に値を小さくしたものと定義する。 このとき、$[K,N]$をみたす素数のみについて、値が重複しない最長の区間を求めこれの先頭の素数を答えよ。

$1<N\leqq2*10^5$、$1≦K≦N$

yukicoder006

解法

しゃくとり法。

しゃくとり、年越しコンテストでやっとバグらせず書けるようになった。 コツは、条件を満たす連続区間を$[s,t)$として、条件を満たさなくなるまで$t$を伸ばして、最後に一つだけ$s$を進めることだと思う。

これは余談ですが、桁に含まれる$9$は無視できるから、今回の$hash$値は$(n-1)\%9 + 1$ ということに後から気がついた

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    #define primeN 400002 
    vector<int > make_prime() {
        vector<int >a;
        bool prime[primeN + 1];// 外部だとハッシュ表みたいになる
        FOR(i, 0, primeN + 1) {
            prime[i] = 1;
        }prime[0] = prime[1] = 0;
    
        for (int i = 2; i <= primeN; i++) {
            if (prime[i]) {
                a.push_back((long long)i);
                for (int j = i * 2; j <= primeN; j += i)
                    prime[j] = 0;
            }
        }
        return a;
    }
    #undef primeN 
    
    LL K, N;
    
    int ans = 0;
    
    int f(int x) {
        int sum = x;
        int ret = sum;
        do {
            sum = ret;
            ret = 0;
            while (sum) {
                ret += sum % 10;
                sum /= 10;
            }
        } while (ret > 9);
        return ret;
    }
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> K >> N;
        vector<int> a = make_prime();
        int i = 0, j = 0;
        while (a[i] < K)i++;
        j = i;
        int ansid = a[i];
        ans = 1;
        VI used(10, 0);
        while (a[i] <= N) {
    
            for (; a[j] <= N && !used[f(a[j])]; j++) { // [i,j)が正しい区間
                used[f(a[j])] = 1;
            }
            if (ans <= j - i) {
                ans = j - i;
                ansid = a[i];
            }
            used[f(a[i])] = 0;
            i++;
        }
        cout << ansid << endl;
        return 0;
    }