[codility] Lesson 12. Euclidean algorithm - ChocolatesByNumbers

https://app.codility.com/programmers/lessons/12-euclidean_algorithm/chocolates_by_numbers/

ChocolatesByNumbers coding task - Learn to Code - Codility

 

• 원형으로 만들어진 초콜릿 조각 N개를 M의 간격으로 먹을 때 먹을 수 있는 초콜릿 조각의 개수
• 다음 조각의 위치는 (X+M) mod N
• N = 10, M =4 이면 0,4,8,2,6
• O(log(N + M))

 

def GCD(a,b):
    if(b==0):
        return a
    else:
        return GCD(b,a%b)

def solution(N, M):
    res = N // GCD(N,M)
    return res