Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
|||||
2015-08-21 19:57:41 Jaswanth
nice problem try to find the pattern |
|||||
2015-04-13 12:22:44 Ankit
my 50th : ) ,nice one Last edit: 2015-04-13 12:24:16 |
|||||
2014-07-19 19:10:21 californiagurl
getting TLE with vector. did anyone get AC using vector? |
|||||
2014-05-31 21:01:04 abhay srinivas
Last edit: 2014-05-31 21:51:08 |
|||||
2014-03-18 08:12:51 fitcat
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. Last edit: 2014-03-19 06:03:35 |
|||||
2014-03-17 05:38:59 californiagurl
Last edit: 2014-03-17 07:18:16 |
|||||
2014-03-07 09:16:15 anurag garg
@nitish rao can you check my solution id:11198262 what is the expected complexity I am getting TLE AC....:) after 30 so many TLE SIGSEGV and WA Last edit: 2014-03-17 16:50:23 |
|||||
2014-03-07 09:16:15 Flago
Case K=1 got me a TLE :D |
|||||
2014-03-07 09:16:15 Kanish_The_Vista
Last edit: 2014-03-06 18:06:07 |
|||||
2014-03-07 09:16:15 Kanish_The_Vista
Last edit: 2014-03-06 18:06:18 |