백준 알고리즘 9613번 - GCD 합

배열로 입력받아서 for문을 두번 돌면서 gcd 쌍의 합을 구하면 되는 문제.

두 수의 gcd를 구하는 방법으로 유클리드 호제법을 사용하였다.

int gcd(int a,int b)
{
    while(b!=0){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

재귀 호출이 싫어서 이렇게 구현했지만, 재귀로도 유클리드 호제법을 구현할 수 있다.

 

int gcd(int a,int b)
{
    while(b!=0){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

 

이것을 기반으로 gcd라는 함수를 만들어서, 배열의 각 원소를 돌면서 gcd 연산을 해주었다.

 

주석처리를 해서 이해하는데 문제가 없을것같다.

// Example program
#include <iostream>
#include <cstdio>
 
using namespace std;
 
//유클리드 호제법으로 최소공약수 구한다.
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
 
int main()
{
    int a;
    int num=0;
    cin>>a;
    //한 개당 최대 1억까지 들어가므로 최대공약수의 합은 int 범위를 넘어갈수 있다
    long long int ans=0;
    //처음에 입력한 값만큼 돈다
    for(int i=1;i<=a;i++){
        int arr[101]={0};
        cin>>num;
        for(int l=1;l<=num;l++){
            scanf("%d",&arr[l]);
        }
        //각각 원소를 짝지어서 gcd를 구한뒤 그 값을 ans에 더해준다
        for(int j=1;j<num;j++){
            for(int k=j+1;k<=num;k++){
                ans+=gcd(arr[j],arr[k]);    
            }
        }
        //ans를 출력하고 초기화한다.
        printf("%d\n",ans);
        ans=0;
    }
    return 0;
}