yukicoder 0006 使いものにならないハッシュ

概要

$n$ に対するハッシュ関数 $h$ を,

• $n$ が一桁なら $h(n) = n$,

• $n$ が二桁以上なら, $n$ の各桁の和を $s$ としたとき, $h(n) = h(s)$

で定める.

$K, N$ が与えられるので, $K$ 以上 $N$ 以下の連続した素数列のうち, 列に含まれる素数の $h$ によるハッシュ値が全て異なるようなもののうち, 長さ最大のものを答えよ.

制約

$1 \le K \le N \le 2 * 10^5$.

解法

尺取りすればいい.

$h(n)$ は $n$ を $9$ で割った余りで決まることに注意すると, 尺取りすらしなくてもよい.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool solve(){
    int k, n;
    cin >> k >> n;
    vector<ll> ps = segsieve(k, n+1);
    pair<int, ll> res(0, 0);
    repsz(i, ps){
        array<int, 9> cnt = {};
        int j;
        for(j = 0; i+j < size(ps); ++j) if(cnt[ps[i+j]%9]++) break;
        chmax(res, make_pair(j, ps[i]));
    }
    cout << res.snd << endl;
    return true;
}