The supply ships

Problem

Obdulia has the only store on the island, and everything she sells arrives by sea. Two ships supply her: one comes by every a days and the other every b days. Today is day 0 and both just unloaded, so the first one is back on day a, the next time on day 2 * a, and so on; the other one does the same with b. Day 0 does not count, because it already happened.

A day when either of the two arrives is a supply day, and when both arrive on the same day it is still one single supply day: it counts once, not twice.

Write a function that takes a, b and n (all three from 1 up) and returns which day supply number n falls on.

With a equal to 2, b equal to 3 and n equal to 5, the supply days are 2, 3, 4, 6, 8... Day 6 is one single day even though both ships arrive, so the fifth supply falls on day 8.

With 4, 6 and 7 the days are 4, 6, 8, 12, 16, 18 and 20: the seventh falls on day 20.

a and b go up to 100 000 and n up to a billion, so the answer can have fourteen digits, and counting day by day never ends.

What you can do is ask, for any given day, how many supplies there were up to that day: the multiples of a that fit, plus the multiples of b that fit, minus the ones counted twice because they are multiples of both at once. That count walks nothing, and with it you can split the range of days in half.

The days when both ships meet are the multiples of the first day they arrive together, and that day is the smallest number that is a multiple of a and of b at the same time: the least common multiple. One way to get it is from the greatest common divisor of the two, and you write that divisor yourself, because JavaScript does not come with one.

Examples

• The one from the example

  2, 3, 5 → 8

• Every four and every six

  4, 6, 7 → 20

• Both ships with the same step

  5, 5, 4 → 20

• One of them comes daily

  1, 4, 10 → 10

• One every two and one every four

  2, 4, 9 → 18

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def supply_day(a, b, n):
    pass

function supplyDay(a, b, n) {
}