SPEC_SET - Special Set
Little boy Sai is fascinated with Natural Numbers. He especially likes Special Sets of order k. A set of numbers S, is called Special Set of order k if, for any two numbers x and y (not necessarily distinct) belonging to S, x should not be equal to k*y.
Now, Sai wants to find the size of maximum possible Special Set formed out of the numbers 1, 2, 3 ... n. Hope you can help him.
Input
First line contains t (1 <= t <= 105), the number of test cases. Next t lines contain two space separated integers n and k.
1 <= n, k <= 108.
Output
For each test case, output on a single line the size of maximal special set.
Example
Input: 1 6 2 Output: 4
Explanation:
For the above case, the maximal Special set is: 1, 3, 4, 5
hide comments
Jaswanth:
2015-08-21 19:57:41
nice problem try to find the pattern |
|
Ankit:
2015-04-13 12:22:44
my 50th : ) ,nice one
|
|
californiagurl:
2014-07-19 19:10:21
getting TLE with vector. did anyone get AC using vector? |
|
abhay srinivas:
2014-05-31 21:01:04
Last edit: 2014-05-31 21:51:08 |
|
fitcat:
2014-03-18 08:12:51
Doesn't a set ensure all members are distinct? I think it should be rephrased as "for any number x belonging to S, k*x does not belong to S." Anyway, nice one.
|
|
californiagurl:
2014-03-17 05:38:59
Last edit: 2014-03-17 07:18:16 |
|
anurag garg:
2014-03-07 09:16:15
@nitish rao can you check my solution id:11198262
|
|
Flago:
2014-03-07 09:16:15
Case K=1 got me a TLE :D |
|
Kanish_The_Vista:
2014-03-07 09:16:15
Last edit: 2014-03-06 18:06:07 |
|
Kanish_The_Vista:
2014-03-07 09:16:15
Last edit: 2014-03-06 18:06:18 |
Added by: | nitish rao |
Date: | 2014-03-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | My own Problem |