om1429888's blog

Please help me solve this problem
By om1429888, history, 2 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't reach the site. Maybe you could copy the statement in here?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you also tell me what's time limit in this task?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 second. and memory is 1536MB.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Not necessary already. I made a little mistake in my code that, however, made me change MAXN constant to 1.5e8 when 1.1e7 is 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

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            its giving a runtime error.SIGSEGV can u explain ur idea briefly?im pretty dumb.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "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.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks. But is there any other algorithm or some other way i can optimize this?

            → Reply