백준온라인저지(BOJ)/#9613//GCD(최대공약수)/C++/유클리드 호제법(Euclidean Algorithm)

24 와 16의 최대 공약수를 구해보자. 여기에서 유클리드 호제법 알고리즘을 사용하면 쉽게 구할 수 있다. 

최대 공약수를 구하고자 하는 두 수에서 큰 수 a 를 작은수 b 로 나눈 나머지 r 과 기존의 작은수 b 

(24, 16) 으로 구한다고 생각하면,

24%16 = r 로 놓고, 

(24, 16) 대신 ( 16, r)에 대해 똑같은 방식으로 연산을 수행하여 숫자를 점점 줄여나간다. 

r 이 0이 되는 순간에 옆에 있는 숫자가 바로 GCD, 최대공약수가 된다. 

#include <algorithm>
#include <iostream>
using namespace std;

int gcd(int a, int b){
    if(b == 0){
        return a;
    }
    else{
        return gcd(b, a%b);
    }
}

int main(){
    int x,y;
    cin>>x>>y;
    if(x<y){
        swap(x,y);
    }
    cout<<gcd(x,y);
    return 0;
}

 

아래는 실행 결과..

8이 나오는구나 

https://www.amcicpc.net/problem/9613

불러오는 중입니다...

그럼 GCD문제를 풀어보자.

Test Case로 받고, 각 Test Case당 가능한 모든 pair의 GCD의 합을 구해서 차례로 출력하는 문제다. 가능한 모든 pair를 찾으면서(순회하면서), 각 pair에 대해서 위에서 정의해둔 gcd (x,y) function을 사용하면 될 것이다. 

코드는 C++ 

#include <iostream>
using namespace std;
int gcd(int x, int y){
    if(y == 0) return x;
    else return gcd(y, x%y);
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int a[111];
        int n;
        cin>>n;
        for(int i = 0; i < n; i++){
            cin>>a[i];
        }
        long long sum = 0;
        for(int i = 0; i < n-1 ; i++){ // Search All the cases that make pairs
            for(int j = i+1; j < n; j++){
                sum += gcd(a[i],a[j]);
            }
        }
        cout << sum << '\n';
    }
    return 0;
}

깔끔하다..