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

 

9613번: GCD 합

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진

www.acmicpc.net

 

[난이도] Silver3
[유형] 수학

[풀이]
최대공약수 구하기
답이 int 범위를 넘어갈 수 있으므로 Long으로

 

import java.io.BufferedReader
import java.io.InputStreamReader
fun gcd(n:Int,m:Int):Int{
    var a=n
    var b=m
    if(a>b) a=b.also{b=a}

    while(a>0){
        var c = b%a
        b=a
        a=c
    }
    return b
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var t = readLine().toInt()
    val arr = IntArray(101)
    while(t-->0){
        val ip=readLine().split(' ')
        val N=ip[0].toInt()
        for(i in 1..N) arr[i-1]=ip[i].toInt()
        var ans:Long=0
        for(i in 0 until N-1){
            for(j in i+1 until N){
                ans+=gcd(arr[i],arr[j])
            }
        }
        println(ans)
    }
}


https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/9613.cpp

+ Recent posts