백준 9613번 c++ 풀이

알고리즘: 유클리드 호제법, 수학, 정수론

코드:

#include <iostream>
#include <vector>

int GCD(int a, int b);
int main(){
    int f;
    scanf("%d",&f);
    
    for(int i = 0; i<f; i++){
        int a;
        long long int result = 0;
        scanf("%d",&a);
        std::vector <int> v(100);
        for(int j= 0; j<a; j++){
            scanf("%d",&v.at(j));
        }
        
        
        for(int j= 0; j<a; j++){
            for(int ij = j+1; ij<a; ij++){
                
                result += GCD(v.at(ij), v.at(j));
                
            }
        }
        printf("%lld\n",result);

    }

    return 0;
}
//a>=b
int GCD(int a, int b){
    int r = a%b; if(r==0){return b;}
    else{return GCD(b,r);}    
}