SPCO - Gopu and Counting Bitwise Prime Numbers
A positive integer is said to be bitwise prime if the sum of all the bits in its binary representation is a prime number.
You are given two integers a and b. You have to output number of bitwise prime numbers between a and b (inclusive).
First line contains T : number of test cases. (1 <= T <= 10^5)
For next T lines, each test case contains two space separated integers a and b. (a <= b). 1 <= a, b <= 10^19.
For each test case, print the number of bitwise prime numbers between a and b (inclusive).
1 3 Output: 0
for c++ use unsigned long long
dp and precomputation, 13th rank :)
@[Laksman] i getting TLE for the second test case,can u please elaborate a little what type of precomputation is nedded ?
What is maximum value of a-b in the test cases ? Is memorization possible ?
anyone plzz provide me with some test cases...i feel like my code is perfect but still getting wa..:(
a and b,both are inclusive?
@Pawankumar P Nothing special but pre-computation makes it faster.
@praveen123 nice question :)
Change Input In Binary Then its simple Dp :D
Nice one !
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM64|
|Resource:||IITK ACA CSE online judge|