파이썬에서 a, b, c로 나누어 떨어지는 수열의 n번째 항을 찾는 프로그램

<시간/>

네 개의 숫자 n, b, c가 있다고 가정합니다. 우리는 a, b 또는 c로 나눌 수 있는 정렬된 수열의 n번째(0인덱싱된) 항을 찾아야 합니다.

따라서 입력이 n =8 a =3 b =7 c =9와 같으면 시퀀스의 처음 9개 항이 [1, 3, 6, 7, 9, 12, 14이므로 출력은 18이 됩니다. , 15, 18].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

, b, c의 최소값이 1과 같으면
- 반환 n
ab :=lcm(a, b), bc :=lcm(b, c), ca :=lcm(a, c)
abc :=lcm(ab, c)
왼쪽 :=1, 오른쪽 :=10^9
왼쪽 <=오른쪽, do
- 중간 :=(왼쪽 + 오른쪽) / 2
- na :=중간 / a의 몫
- nb :=중간 / b의 몫
- nc :=mid / c의 몫
- nab :=중간 / ab의 몫
- nbc :=mid / bc의 몫
- nca :=중간 / ca의 몫
- nabc :=mid / abc의 몫
- numterms :=na + nb + nc - nab - nbc - nca + nabc
- 숫자> n이면
  - 오른쪽 :=중간 - 1
- 그렇지 않으면 numterms
- 왼쪽 :=중간 + 1
그렇지 않으면
- 반환 mid - (mid mod a, mid mod b, mid mod c)의 최소값

반환 -1

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

import math
def lcm(a, b):
   return (a * b) // math.gcd(a, b)
class Solution:
   def solve(self, n, a, b, c):
      if min(a, b, c) == 1:
         return n
      ab, bc, ca = lcm(a, b), lcm(b, c), lcm(a, c)
      abc = lcm(ab, c)
      left, right = 1, 10 ** 9
      while left <= right:
         mid = (left + right) // 2
         na = mid // a
         nb = mid // b
         nc = mid // c
         nab = mid // ab
         nbc = mid // bc
         nca = mid // ca
         nabc = mid // abc
         numterms = na + nb + nc - nab - nbc - nca + nabc
         if numterms > n:
            right = mid - 1
         elif numterms < n:
            left = mid + 1
         else:
            return mid - min(mid % a, mid % b, mid % c)
      return -1
ob = Solution()
n = 8
a = 3
b = 7
c = 9
print(ob.solve(n, a, b, c))

입력

8, 3, 7, 9