[C++][백준 21920] 서로소 평균

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

풀이1

x의 소인수를 저장해두고, 입력된 수들을 x의 소인수들로 나눠서 서로소인지 여부를 확인한다

 

제출 코드

#include <iostream>
#include <vector>
using namespace std;

int arr[500001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cin >> x;
    vector<int> v;
    // x의 소인수 구하기
    for (int i = 2; i <= x; i++)
    {
        if (x % i == 0)
        {
            v.push_back(i);
            while(x % i == 0)
                x = x / i;
        }
    }

    int cnt = 0;
    long long sum = 0;
    // 각 입력값들이 x의 소인수를 약수로 가지는지 확인
    for (int i = 0; i < n; i++)
    {
        bool e = false;
        for (auto& s : v)
        {
            if (arr[i] % s == 0)
            {
                e = true;
                break;
            }
        }
        if (!e)
        {
            cnt++;
            sum += arr[i];
        }
    }

    cout << sum / float(cnt);
}

 

풀이2

서로소라는 것은 두 수의 최대공약수가 1인 수라는 의미이다

이를 그대로 해석하여 gcd 함수를 이용해 구현이 가능하다

 

제출 코드

#include <iostream>
#include <numeric>
using namespace std;

int arr[500001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cin >> x;
    int cnt = 0;
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (gcd(arr[i], x) == 1)
        {
            cnt++;
            sum += arr[i];
        }
    }

    cout << sum / float(cnt);
}

gcd 함수는 numeric 헤더를 추가하고 사용 가능하다