[백준] 21920번 : 서로소 평균 (C++)

21920번 : 서로소 평균

---

문제)

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

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

 

 

 

입력 :

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

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

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

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

 

 

 

출력 :

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

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

 

 

 

 

 

풀이)

 

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int n, x;
int numbers[500010];
 
// 유클리드 호제법
// 두 수의 최대 공약수를 구해, 그 결과 값이 1이라면 
// 두 수는 서로소이다.
int get_gcd(int big, int small)
{
    if (small == 0)
    {
        return big;
    }
    else
    {
        return get_gcd(small, big % small);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> numbers[i];
    }
 
    cin >> x;
 
    double cnt = 0;
    double total = 0;
 
    for (int i = 0; i < n; i++)
    {
        int num = numbers[i];
        if (get_gcd(x, num) == 1)
        {
            cnt++;
            total += numbers[i];
        }
    }
    cout.precision(7);
    cout << total / cnt;
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/21920 

21920번: 서로소 평균