The n-th multiple of either number
Reported in interviews at (where)
List, from the smallest up, every positive whole number that is divisible by a, by b, or by both. A number divisible by both is listed once.
For each test, print the n-th number in that list. n can be as large as a billion, so walking the list one number at a time is far too slow.
Input
The first line holds T, the number of tests. Each test is one line holding three whole numbers: a, b and n.
Output
For each test, one line: the n-th number divisible by a or by b.
- Input
3
3 5 6
4 6 5
7 7 3- Output
12
16
21
- The list starts 3, 5, 6, 9, 10, 12: the sixth number is 12.
- The list starts 4, 6, 8, 12, 16: 12 is divisible by both and is listed once.
- With a and b the same, the list is just the multiples of 7.
Limits
1 <= T <= 10001 <= a, b <= 400001 <= n <= 1000000000
Hints
Hint 1
How many numbers from 1 to x are in the list? x / a of them divide by a and x / b by b, but the ones divisible by both were counted twice: those are the multiples of the least common multiple of a and b.
Hint 2
That count only grows as x grows, so binary search for the smallest x whose count reaches n. The answer is at most n times the smaller of a and b.
Where this was reported
- GlobalLogic, On-campus interview, 2017 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
