[백준 알고리즘/C++] 2981 검문

 

 

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다 (?)

먼저 근처에 보이는 숫자 N개를 종이에 적는다.

그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 문제

 

 

결과부터 말하자면

N개의 입력값의 차잇값들 중에서 최대공약수를 구하고

그 최대공약수의 약수들을 구해 출력하면 된다

 

그럼 왜 이런 결론이 나왔느냐..? 수학적으로 접근해서 구해야 한다

---

1. M으로 나누었을 때 나머지가 같다고 했으니 예시로 주어진 6, 34, 38은 이렇게 표현할 수 있다

 

ㄱ. 6 = M*몫1+나머지

ㄴ. 34 = M*몫2+나머지

ㄷ. 38 = M*몫3+나머지

 

2. 위 식에서 나머지 부분을 없애기 위해 ㄴ-ㄱ, ㄷ-ㄴ를 해보자

 

ㄴ-ㄱ : 34-6 = M*(몫2 - 몫1)

ㄷ-ㄴ : 38-34 = M*(몫3 - 몫2)

 

다시 정리하면

 

28 = M*(몫2 - 몫1)

4 = M*(몫3 - 몫2)

 

가 된다

 

3. 위 식은 곧 M에다 뭔가를 곱하면 28과 4가 된다는 말이다

     다시 말해 M은 28과 4의 최대공약수이다

 

4. M의 약수도 마찬가지로 나머지를 같게 만든다

---

뭐 이런 과정으로 위와 같은 결론을 도출할 수 있다

어려워서 검색함... ㅠㅠ

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int gcd_func(int a, int b) {
    if (b == 0) return a;
    return gcd_func(b, a % b);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, m;
    cin >> n;
 
    vector<int> v;
    for (int i = 0; i < n; i++) {
        cin >> m;
        v.push_back(m);
    }
 
    sort(v.begin(), v.end());
 
    //차잇값들의 최대공약수 구하기
    int gcd = v[1] - v[0];
    for (int i = 2; i < n; i++) {
        gcd = gcd_func(v[i] - v[i - 1], gcd);
    }
 
    //약수 모두 구하기
    int i;
    vector<int> res;
    for (i = 2; i < sqrt(gcd); i++) {
        if (gcd % i == 0) {
            res.push_back(i);
            res.push_back(gcd/i);
        }
    }
 
    if (i * i == gcd) res.push_back(i);
    res.push_back(gcd);
 
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << ' ';
    }
}

 

참고로 sort 안해주면 당연히!! 매우 당연히 틀릴 수 밖에 없다

이 당연한걸 또 틀리는 나