NOSQ - No Squares Numbers
A square free number is defined as a number which is not divisible by any square number.
For example, 13, 15, 210 are square free numbers, where as 25 (divisible by 5*5), 108 (divisible by 6*6), 18 (divisible by 3*3) are not square free numbers. However number 1 is not considered to be a square and is a squarefree number.
Now you must find how many numbers from number a to b, are square free and also have a digit d inside it.
For example for in the range 10 to 40 te squarefree numbers having digit 3 are 13, 23, 30, 31, 33, 34, 35, 37, 38, 39
Input
The first line contains an integer T, which is the number of test-cases
Then follow T lines, each containing 3 integers a, b and d.
1 <= T <= 20,000
1 <= a <= b <= 100,000
0 <= d <= 9
Output
Print one integer which is the required number as described in the problem statement.
Example
Input: 3 10 40 3 1 100 4 1 100000 7 Output: 10 9 26318
hide comments
P_Quantum:
2014-05-31 21:29:23
nice prblm!! |
|
innovolt:
2014-04-13 18:53:12
easy 1 |
|
Alexandre Henrique Afonso Campos:
2014-02-17 01:31:02
I'm glad that I finally got AC. I had to translate a good idea from Python to C++ to get rid of TLE. I still feel that I have to reduce just a bit to receive AC also in Python. |
|
Jumpy:
2014-01-30 16:46:21
finally did it thanks nammo.. |
|
Mitch Schwartz:
2013-07-20 21:09:49
@Hariharan: Read the problem statement carefully; "square-free" is not the same as "not a perfect square". |
|
Hariharan :
2013-07-20 18:34:18
How is the solution for the 2nd test case 9? We have- 14,24,34,40,41,42,43,44,45,46,47,48,54,74,84,94- there're 16 numbers not 9. |
|
saket diwakar:
2013-01-21 14:27:02
nice one......:) |
|
Praveen Vaka:
2012-06-06 05:11:30
@sandeep pandey I had already solved the question before posting the comment. I just wanted others to realize that there are 20,000 test cases and a trivial algorithm will not work. Kindly consider editing your comment since it gives away the approach for the problem. |
|
sandeep pandey:
2012-04-10 17:53:20
@Praveen Vaka:You are expected to apply BinarySearch for answering each query. |
|
M Misbachul Huda:
2011-11-02 16:32:57
he ndul, kon mbujuk ta 3 second iku?? |
Added by: | .:: Pratik ::. |
Date: | 2011-03-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |