Блог пользователя _notpalindrome_

Автор _notpalindrome_, история, 6 лет назад, По-английски

Seems like the range is huge. How can I optimizely solve it. Any hint would be greatly appreciated. Thanks. :) Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1474

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
constexpr int MAXN = (int)1e6 + 1;
bool is_composite[MAXN];
int digit_sum[MAXN];
int partial_sum[MAXN];

digit_sum[1] = 1;
for (int i = 2; i < MAXN; ++i) {
  digit_sum[i] = digit_sum[i / 10] + i % 10;
  if (!is_composite[i] && (int64_t) i * i < MAXN) {
    for (int j = i * i; j < MAXN; j += i) {
      is_composite[j] = true;
    }
  }
  partial_sum[i] = partial_sum[i - 1] + (!is_composite[i] && !is_composite[digit_sum[i]]);
}
int queries;
in >> queries;
for (int query = 0; query < queries; ++query) {
  int l, r;
  in >> l >> r;
  out << partial_sum[r] - partial_sum[l - 1] << '\n';
}