BOJ21920 서로소 평균

선행지식

유클리드 호제법

문제

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

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

접근방식 1 (유클리드 호제법)

쉬운 문제다.
최소공배수가 1이면 서로소이다.
그리고 그것을 기호로 표현 하면 gcd(A,X)==1 이 된다.

gcd(A,X)는 유클리드 호제법으로 구할 수 있는데
유클리드 호제법은
a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 출처 : 위키피디아

남은건 그냥 구현하면 끝난다.

#include <iostream>
#include <vector>
using namespace std;
int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,cnt=0;
    double sum=0;
    vector<int> a;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> m;
        a.push_back(m);
    }cin >> m;
    for(int i=0; i<n; i++){
        if(gcd(a[i],m)==1){
            sum+=a[i];
            cnt++;
        }
    }cout << sum/cnt;
}