Bruteforceboy's blog

By Bruteforceboy, history, 12 months ago, ,

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

 » 12 months ago, # |   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'; } 
 » 12 months ago, # |   0 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 :)