結果

問題 No.6 使いものにならないハッシュ
ユーザー satonakatakumisatonakatakumi
提出日時 2021-08-07 19:22:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 4,052 bytes
コンパイル時間 2,373 ms
コンパイル使用メモリ 209,580 KB
実行使用メモリ 53,840 KB
最終ジャッジ日時 2023-10-18 23:39:15
合計ジャッジ時間 4,309 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
53,656 KB
testcase_01 AC 18 ms
53,660 KB
testcase_02 AC 19 ms
53,780 KB
testcase_03 AC 18 ms
53,728 KB
testcase_04 AC 18 ms
53,732 KB
testcase_05 AC 18 ms
53,780 KB
testcase_06 AC 18 ms
53,820 KB
testcase_07 AC 18 ms
53,776 KB
testcase_08 AC 18 ms
53,784 KB
testcase_09 AC 18 ms
53,724 KB
testcase_10 AC 18 ms
53,656 KB
testcase_11 AC 18 ms
53,732 KB
testcase_12 AC 18 ms
53,832 KB
testcase_13 AC 18 ms
53,692 KB
testcase_14 AC 19 ms
53,724 KB
testcase_15 AC 18 ms
53,824 KB
testcase_16 AC 18 ms
53,776 KB
testcase_17 AC 18 ms
53,832 KB
testcase_18 AC 18 ms
53,780 KB
testcase_19 AC 19 ms
53,828 KB
testcase_20 AC 18 ms
53,828 KB
testcase_21 AC 18 ms
53,692 KB
testcase_22 AC 19 ms
53,828 KB
testcase_23 AC 18 ms
53,828 KB
testcase_24 AC 18 ms
53,828 KB
testcase_25 AC 18 ms
53,780 KB
testcase_26 AC 18 ms
53,836 KB
testcase_27 AC 18 ms
53,820 KB
testcase_28 AC 18 ms
53,784 KB
testcase_29 AC 18 ms
53,840 KB
testcase_30 AC 18 ms
53,836 KB
testcase_31 AC 18 ms
53,828 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using u32 = std::uint32_t;
using u64 = std::uint64_t;

template<class T> bool chmax(T &a, const T b) {
    if (b > a) {
        a = b;
        return false;
    }
    return true;
}

u64 useless_hash(u64 n) { return (n == 0) ? 0 : ((n % 9 == 0) ? 9 : n % 9); }

#define MAX 200200
const u32 block_size = 1 << 19;

u32 s_inner, prime_cnt_inner, sq_inner[65536], sp_inner[65536], primes_inner[26500010];
u64 wheel_inner[15015], is_composite_inner[8192], mask_inner[12][62][8192];

inline void setbit_(u64* ar, u32 bit) { ar[bit >> 6] |= (1ull << (bit & 63));}
inline u32 get_idx_(u32 i, u32 j) {
    if (sq_inner[j] > i) return (sq_inner[j] - i) >> 1;
    u32 x = sp_inner[j] - i % sp_inner[j];
    if (!(x & 1)) x += sp_inner[j];
    return x >> 1;
}
void small_sieve_() {
    for (u32 i = 2; i * i < 65536; i++) for (u32 j = i * i; j < 65536 && !sp_inner[i]; j += i) sp_inner[j] = 1;
    for (u32 i = 2; i < 65536; i++) if (!sp_inner[i]) sp_inner[s_inner] = i, sq_inner[s_inner++] = i * i;
}
void process_block_(u32 i) {
    u32 j, k, l, d, m, x, lim = i + block_size, idx = i % 15015, chunk = 0;
    idx = (idx + ((idx * 105) & 127) * 15015) >> 7;
    for (j = 0; (j << 7) < block_size; j += chunk, idx = 0) {
        chunk = std::min(15015 - idx, (block_size >> 7) - j);
        memcpy(is_composite_inner + j, wheel_inner + idx, sizeof(u64) * chunk);
    }
    if (!i) is_composite_inner[0] = (is_composite_inner[0] | 1) & ~110ULL;
    l = block_size >> 1, m = block_size >> 7;
    for (j = 6; j < 18 && i; j++) for (x = get_idx_(i, j), k = 0, d = j - 6; k < m; k++) is_composite_inner[k] |= mask_inner[d][x][k];
    for (j = (i == 0) ? 6 : 18; j < s_inner && sq_inner[j] < lim; j++) for (x = get_idx_(i, j); x < l; x += sp_inner[j]) setbit_(is_composite_inner, x);
}
void populate_primes_(u32 i, u32 n) {
    for (u32 j = 0; (j << 7) < block_size; j++) {
        u64 x = ~is_composite_inner[j];
        while (x) {
            u32 p = i + (j << 7) + (__builtin_ctzll(x) << 1) + 1;
            if (p <= n) primes_inner[prime_cnt_inner++] = p;
            x ^= (-x & x);
        }
    }
}
void fast_sieve_(u32 n) {
    small_sieve_();
    for (u32 i = 1; i <= 5; i++) for (u32 j = i + (i > 3); j < 960960; j += sp_inner[i]) setbit_(wheel_inner, j);
    for (u32 i = 6; i <= 17; i++) for (u32 j = 0; j < sp_inner[i]; j++) for (u32 k = j; k < (block_size >> 1); k += sp_inner[i]) setbit_(mask_inner[i - 6][j], k);
    if (n >= 2) primes_inner[prime_cnt_inner++] = 2;
    for (u32 i = 0; i <= n; i += block_size) {
        process_block_(i);
        populate_primes_(i, n);
    }
}
std::vector<u32> enumerate_primes(u32 k, u32 n, u32 a = 1, u32 b = 0) {
    fast_sieve_(n);
    std::vector<u32> res;
    for (u32 u = b; u < prime_cnt_inner; u += a) {
        if (primes_inner[u] >= k) {
            res.push_back(primes_inner[u]);
        }
    }
    return res;
}

int solver(u32 k, u32 n) {
    auto t = enumerate_primes(k, n);
    std::vector<std::pair<u32, u32>> p;
    for (u32 i = 0; i < static_cast<u32>(t.size()); ++i) {
        p.emplace_back(t[i], useless_hash(t[i]));
    }
    int maxv = 0, ans = 0, l2 = -1;
    std::vector<int> t2(10, -1);
    for (int i = 0; i < p.size(); i++) {
        chmax(l2, t2[p[i].second]);
        if (i - l2 >= maxv) {
            maxv = i - l2;
            ans = p[l2 + 1].first;
        }
        t2[p[i].second] = i;
    }
    return ans;
}

bool is_space(int ch) {
  return ch == ' ' || ch == '\n' || ch == '\t' || ch == '\r' || ch == '\f' ||
         ch == '\v';
}
bool is_digit(int ch) {
  return ch == '1' || ch == '2' || ch == '3' || ch == '4' || ch == '5' ||
         ch == '6' || ch == '7' || ch == '8' || ch == '9' || ch == '0';
}
u32 read_int() {
  u32 ret = 0;
  int ch = getchar_unlocked();
  while (is_space(ch))
    ch = getchar_unlocked();
  for (; is_digit(ch); ch = getchar_unlocked())
    ret = (ret * 10) + (ch - '0');
  ungetc(ch, stdin);
  return ret;
}

int main() {
    u32 k = read_int();
    u32 n = read_int();
    printf("%d", solver(k, n));
    return 0;
}
0