[Codility] 12.1 ChocolatesByNumbers

ChocolatesByNumbers 문제 풀기

1. 원형으로 만들어진 초콜릿 조각 $N$개를 $M$의 간격으로 먹을 때, 먹을 수 있는 초콜릿 조각의 개수는? 단, 먹었던 조각으로 오면 멈춘다.
2. 초콜릿 조각의 위치는 $0 \leq x \leq N-1$이고, 현재 조각의 위치를 $x$라 하면, 다음 조각의 위치는 $(x+M) \mod N$이다
3. $N=10, M=4$일 때, 0, 4, 8, 2, 6의 조각을 먹을 수 있다.
4. $N, M \leq 10^9$

시뮬레이션을 돌리면 $O(N+M)$일 것이므로 당연히 시간초과가 뜬다.
단순하게 $N$이 $M$의 배수라고 생각하자. 그러면 $N/M$개의 조각을 먹을 수 있다.
만약 $N$과 $M$이 서로소 관계라고 하자. 그러면 $N$개의 모든 조각을 먹을 수 있다.
그렇다면 $gcd(N, M)=g$라고 하자. 그러면 $N/g$개의 조각을 먹을 수 있다.

이제 관계를 알았다. 배수, 서로소든 관계없이 $N/gcd(N, M)$개의 조각을 먹을 수 있다.

파이썬에 gcd() 키워드가 있는 것 같다. 그래서 getGCD()를 새로 작성해서 만들었다.
시간복잡도는 getGCD()만 영향을 미치므로 앞에서 보았듯이 $O(\log(N+M))$이다.

def getGCD(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return getGCD(b, a % b)

def solution(N, M):
    return N // getGCD(N, M)