[C++] 셋 이상 수의 최대공약수(GCD) 구하기

- 두 수의 GCD를 구해주는 GCD 함수를 정의하고

int GCD(int x, int y) {
    while(true) {
        if(x>y) {
            x = x%y;
            if(x==0) return y;
        } else {
            y = y%x;
            if(y==0) return x;
        }
    }
}

 

- 연속한 데이터끼리 GCD를 구한다, 반복적으로 적용하기 위해 cyclic하게 동작할 수 있는 Queue 자료형 활용

- Queue에 데이터가 한 개 남는다면 그것이 GCD 일 것. (최적화: GCD 리턴값 1이면 바로 break)

    queue<int> q; // data

    int x1, x2, gcd;
    while(true) {
        x1 = q.front();
        q.pop();
        if(q.empty()) {
            gcd = x1;
            break;
        }
        x2 = q.front();
        q.pop();
        q.push(GCD(x1,x2));
    }

 

 

- 순서대로 앞에서부터 쭉 비교해도 되겠다

    gcd = GCD(v[0], v[1]);
    for(int i=2; i<N; i++) {
        gcd = GCD(gcd, v[i]);
        if(gcd==1) break;
    }