A festival strings up lanterns with timers. Lantern i flashes on every day that is a multiple of periods[i] (days periods[i], 2·periods[i], ...). The organisers want to know on how many days in 1..days every lantern flashes at once, for the fireworks.
Write together_days(periods: list[int], days: int) -> int.
together_days([4, 6], 30) # 2 (days 12 and 24)
together_days([3, 5, 7], 100) # 0 (the first common day is 105)
together_days([2, 2, 8], 16) # 2 (days 8 and 16)
together_days([1], 5) # 5
All lanterns flash together exactly on the common multiples of the periods, i.e. on the multiples of their least common multiple. Fold it in one period at a time with lcm(a, b) = a // gcd(a, b) * b.
Watch the size: with 10^5 lanterns of pairwise coprime periods near 10^9, the true LCM has millions of digits and computing it takes far too long. But once the running LCM is bigger than days, the answer is already 0 and can't change, so stop right there.
Constraints: 1 <= len(periods) <= 10^5, 1 <= periods[i] <= 10^9, 1 <= days <= 10^18. math.gcd is fine to use (or write Euclid's a, b = b, a % b loop yourself).
Show hint
L = 1; for each p: L = L // gcd(L, p) * p, and if L > days: return 0. At the end, return days // L.