i have been trying alot but cant comeup with a solution,i thought using segmented sieve but it gives tle. https://www.spoj.com/problems/BSPRIME/
BSPRIME — Binary Sequence of Prime Number no tags Binary Sequence of Prime Number is a binary sequence that created by converting prime number to base-2 (Without leading zeros):
(2)10=(10)2 (3)10=(11)2 (5)10=(101)2 (7)10=(111)2 ...
If all base-2 of prime number joined, then we get the binary sequence like this: 10111011111011110110...
Now your task is to count how many digit '1' appear in the first N terms of the sequence, example:
-->If N=3, digit '1' appear 2 times: 101110... -->If N=10, digit '1' appear 8 times: 1011101111101...
Input The first line is an integer T(1 ≤ T ≤ 50,000), denoting the number of test cases. Then, T test cases follow.
For each test case, there is an integer N(0 ≤ N ≤ 150,000,000) written in one line.
Output For each test case, output the number of digit '1' appear in the first N terms of the sequence
Example Input: 3 3 10 50
Output: 2 8 36
I can't reach the site. Maybe you could copy the statement in here?
updated
Can you also tell me what's time limit in this task?
1 second. and memory is 1536MB.
Bruh, I can only optimize my program to around 1.9 secs on my laptop. Maybe it will work faster on server?
Maybe it'll fit in the system TL. You can try it: Code
Oops, it answers the wrong question, I'll fix it in a minute.
its giving TLE. i found another solution but i cant understand it. that guy said to divide it into segments reducing the time but i didnt understand how to do it. https://www.quora.com/How-do-I-solve-a-BSPRIME-on-SPOJ here is the article.
Not necessary already. I made a little mistake in my code that, however, made me change
MAXNconstant to1.5e8when1.1e7is enough. Last 20 minutes I was writing and debugging linear sieve and found out there was no need haha. Here is my code with the usual sieve.The idea is, as I think, the same as yours: precalc sequence and the simply calculate prefix sums on it.
Code
its giving a runtime error.SIGSEGV can u explain ur idea briefly?im pretty dumb.
Oh, sorry, completely forgot to check my cf messages. My cod works locally, idk what's with the seg fault. Idea is pretty simple. Let's generate first 1.5e7 digits of the sequence and answer the queries. To do it, we use the sieve and simply do what we wanted: for each prime we add it's binary to sequence.
"that guy said to divide it into segments reducing the time"
This got me interested. Apparently he optimized something that did not need optimization. A segmented sieve only speeds up the space complexity, but not time complexity.
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve
As systy said already, the normal sieve seems to barely be fast enough.
Thanks. But is there any other algorithm or some other way i can optimize this?
Yup, as I said, there is a linear Eratosthenes sieve. You can read about it somewhere on the internet. However, there is no need in doing this, i think. Usual sieve works here in this task.
yeah, and one fact we need to recognize is that $$$O(log log n)$$$ is usually very small (though not "insignificant")
https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#memory-consumption-and-speed-of-operations
This site is pretty good for these kinds of questions. Apparently The Segmented sieve is better, it may not use less operations, but because of caching the algorithm will run faster.