Bruteforceboy's blog

By Bruteforceboy, history, 12 months ago, In English,

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it
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';
}
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

firstly with Sieve find out prime up to 10e7 take o(nlogn) Then take an array of 10e7. if any number is digit prime then do it. arr[number]+=arr[number-1] .it take O(n). next for each Quary a b, you find answer just o(1) time by doing this arr[b]-arr[a]. Happy coding :)