[Codility] 12. Euclidean algorithm (ChocolatesByNumbers)

12. Euclidean algorithm

최대공약수, 최소공배수 알고리즘

https://hyunjini.tistory.com/54

최대공약수 최소공배수 알고리즘 (유클리드 호제법)

12.1 ChocolatesByNumbers

Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N − 1.After eating a chocolate you leave only a wrapper.You begin with eating chocolate number 0.More precisely, if you ate chocolate number X, then you will next eat the chocolate with number (X + M) modulo N (remainder of division).You stop eating when you encounter an empty wrapper. Write a func that, given two positive integers N and M, returns the number of chocolates that you will eat.

정수 N은 원 안에 배열된 0부터 N - 1까지의 숫자의 초콜릿들의 수를 나타냅니다.여러분은 초콜릿을 먹기 시작합니다. 초콜릿을 먹은 후에는 포장지만 남깁니다.먼저 0번 초콜릿을 먹는 것으로 시작하고, 다음 M-1 초콜릿이나 포장지를 생략하고, 다음 M-1 초콜릿이나 포장지를 먹는 것으로 시작합니다.더 정확하게 말하면, 만약 여러분이 숫자 X인 초콜릿을 먹었다면, 다음은 숫자 (X + M) 모듈론 N(나눗셈의 나머지)인 초콜릿을 먹을 것입니다.빈 포장지를 만나면 먹는 것을 멈추게 됩니다.두 개의 양의 정수 N과 M이 주어졌을 때, 당신이 먹을 초콜릿의 수를 반환합니다

 

 

$$ \frac{(NM)}{(MGCD)} $$

다시 만나는 지점이 중요!

→최소공배수 사용→두수의 곱/(최대공약수)

최소공배수를 M으로 나눈것

def solution(N, M):
   return N//gcd(N, M)
def gcd(a, b):
   if a % b == 0:
      return b
   else:
      return gcd(b, a % b)