[백준 / Go] 21920번: 서로소 평균

문제

21920번: 서로소 평균

효성이는 길이가 N인 수열 A에서 X와 서로소인 수들을 골라 평균을 구해보려고 한다.

효성이를 도와 이를 계산해주자.

입력

첫 번째 줄에 입력될 수들의 개수 N이 주어진다. (2≤ N ≤500,000)

두 번째 줄에는 수열 A를 이루는 자연수 A_i 가 공백으로 구분되어 주어진다. (2≤A ≤1,000,000) 

수열 A에 X와 서로소인 수가 최소 1개 이상 존재한다.

마지막 줄에는 X가 주어진다. (2≤ X ≤1,000,000)

출력

첫째 줄에 수열 A에서 X와 서로소인 수들의 평균을 출력한다.

절대/상대 오차는 10^-6까지 허용한다.

---

문제 이해하기

 서로 다른 수들의 공약수가 1이외에 존재하지 않는 경우 이를 서로소라고 합니다. 이 문제에서는 N개의 수들 각각과 X의 최대공약수를 구하여 최대공약수가 1인 경우에 두 수가 서로소임을 확인할 수 있습니다. 

---

코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	scanner = bufio.NewScanner(os.Stdin)
	writer  = bufio.NewWriter(os.Stdout)
	N, X    int
	arr     []int
)

func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanWords)

	Setup()
	Solve()
}

func Setup() {
	N = scanInt()
	arr = make([]int, N)
	for i := 0; i < N; i++ {
		arr[i] = scanInt()
	}
	X = scanInt()
}

func Solve() {
	sum := 0
	cnt := 0

	for i := 0; i < N; i++ {
		if gcd(X, arr[i]) == 1 {
			sum += arr[i]
			cnt++
		}
	}

	if cnt == 0 {
		fmt.Fprintln(writer, 0)
	} else {
		fmt.Fprintf(writer, "%.6f\n", float64(sum)/float64(cnt))
	}
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}

	return a
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func mustParseInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func scanInt() int {
	return mustParseInt(scanString())
}

시간: 124 ms
메모리: 5184 KB
분류: 수학, 정수론, 유클리드 호제법

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!