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
Praveen Vaka:
2011-07-22 09:35:36
Didn't realize that there could be 20,000 test cases. O(T*(b-a)) would lead to TLE mostly at least mine was with precomputation taking less than 1/10th of a second. |
|
kanishka:
2011-06-24 13:00:13
is thr any need to precompute it....??
|
|
Jay Pandya:
2011-06-23 21:27:58
good one..!! |
|
Suprabh Shukla:
2011-06-22 11:43:03
@Pratik: I think O(T*(b-a)) can still be large enough to tle on the given constraints |
|
Egor:
2011-03-11 00:50:23
be careful with borders! |
|
.:: Pratik ::.:
2011-03-10 14:55:28
Rejudge with a stricter (still very lenient time limit). The original contest was for noobs who didn't know of a very fast method to do IO in Java and hence had higher time limits. Sorry to all, I just saw a O( T*(b-a) ) solution clear. |
|
Jordan Spell:
2011-03-09 19:21:50
Nevermind! Last edit: 2011-03-09 13:22:20 |
|
Knight:
2011-03-09 19:21:50
i think the output for 1 100000 7 is
|
|
.:: Pratik ::.:
2011-03-09 19:21:50
This is a very trivial problem. Should I move to tutorial, or anybody has an idea for challenge? (Lowest source code)
|
Added by: | .:: Pratik ::. |
Date: | 2011-03-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |