Submit | All submissions | Best solutions | Back to list |
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
Added by: | .:: Pratik ::. |
Date: | 2011-03-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
hide comments
|
|||||||
2023-03-03 17:54:52
nice problem |
|||||||
2023-02-07 13:15:03
Thanks for the contribution Can't believe I am getting such well framed exercises to do for free :) |
|||||||
2020-09-11 09:00:18
i am not getting it , anyone knows where to find the solution |
|||||||
2019-11-11 15:26:23
Getting TLE even after precomputation any suggestion?? |
|||||||
2019-08-08 13:02:51
precomputation and t*(b-a) give tle |
|||||||
2019-05-09 21:57:32 cegprakash
author, plz remove spoilers from comments. Encourage others to stop giving away the solution. |
|||||||
2018-01-09 09:55:53
Great problem. Constraints are set wisely so a well designed Python code will pass in a fraction of a TL while a solution with clunky C-style loops with "same complexity" will probably TLE. I'd encourage Python beginners to experiment on this problem because learning the pythonic techniques that can significantly speed up your code here can make difference between AC and TLE in many other problems on SPOJ. |
|||||||
2018-01-07 12:51:23
nice problem :) |
|||||||
2017-11-17 06:12:35
Nice problem use prefix array |
|||||||
2016-09-14 23:52:22 saurabh jain
nice problem |