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.



First line contains t(1<=t<=105), the number of test cases. Next t lines contain two space separated integers n and k.



For each test case, output on a single line the size of maximal Special set.


6 2

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

Last edit: 2015-04-13 12:24:16
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.

Last edit: 2014-03-19 06:03:35
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
what is the expected complexity I am getting TLE
after 30 so many TLE SIGSEGV and WA

Last edit: 2014-03-17 16:50:23
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
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:My own Problem