BSPRIME - Binary Sequence of Prime Number
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
hide comments
|
annaadu:
2022-10-05 12:16:12
easy one... |
|
|
annaadu:
2022-10-05 12:15:28
peace of cake :))) |
|
pikachu_69:
2022-07-26 21:07:58
can someone please help me,how to do this? |
|
nadstratosfer:
2021-03-06 09:28:39
majid, you've hammered so many TLE's, WA's and NZEC's that the 120-submission long SPOJ history doesn't even fully show it, then you switched to CPP and proceeded to hit another 16 WA's and NZEC's before your first AC. I can't even imagine the stupor you find yourself in solving what you consider, as opposed to this, a difficult task, but are you really sure it's the problem that's stupid? |
|
majid:
2021-03-06 08:31:47
I tried 1000000 ways to solve this STUPID problem in CSHARP but TLE after TLE...
|
|
sowmiksarker:
2020-09-25 16:43:34
Finally solved it! Nice problem. |
|
|
nadstratosfer:
2018-09-04 18:13:22
Unexpected AC with kindof a prototype of a solution. Began thinking about solving this one 3 days ago but didn't like my initial ideas; woke up with better ones and there we go. This is how the best problems work, forcing my brain to work on them even when I don't intend to =) |
|
hodobox:
2017-10-10 21:04:34
I was running out of optimizations, but Eratosthenes barely made it through :P |
|
devendrap:
2016-06-24 15:04:47
Till: 11753933 Last edit: 2016-06-24 15:05:15 |
|
vishu:
2015-08-14 16:23:23
@Tjandra Sir can u please tell what improvents can I make in my code or I need to change my brute force approach?
|
| Added by: | Tjandra Satria Gunawan |
| Date: | 2012-07-12 |
| Time limit: | 1s |
| Source limit: | 10000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Resource: | Own Problem |
RSS