[C++] 2981번 검문 - 수학, 정수론, 유클리드 호제법

1. 문제

• 숫자 N개가 있다. 이를 M으로 나누었을 때 나머지가 모두 같게 되는 M을 찾고자 한다. \((M > 1)\)
• 가능한 M을 모두 찾으시오.

<입력>

• - 1 -   \(N(2 \leq N \leq 100)\)
• - N개의 줄 -   \(1 \leq num \leq 1,000,000,000\)
  • 같은 수가 2번 이상 주어지지 않음.
  • 항상 M이 하나 이상 존재함

<출력>

• 가능한 M을 공백으로 구분하여 모두 출력한다. M은 증가하는 순서대로 출력한다.

2. 재정의

• \(num[1] \equiv ... \equiv num[N-1] (mod M)\)을 만족하는 1이 아닌 M 모두 구하기

3. 해결 방법

• num[i] - num[1]의 GCD의 1이 아닌 모든 약수를 구한다.
• 유클리드 호제법을 이용하여 GCD를 구하고 sqrt(GCD)까지 탐색해서 약수를 구한다.

4. 실수한 점, 개선할 점

• 차이를 구할 때 음수가 나올 수 있으므로 처음에 num배열을 정렬한 후 사용하자.

 

<코드>

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int MAX_N = 101;

// <문제>
// 숫자의 개수 N
int N;
// 수열
int num[MAX_N];

// <유클리드 호제법>
int gcd;
vector<int> devisor;

void input() {
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> num[i];
}

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);
    
    input();
    
    sort(num, num+N-1);
    
    gcd = num[2]-num[1];
    for(int i=3; i<=N; i++)
        gcd = GCD(num[i]-num[1], gcd);
    
    for(int i=1; i<=sqrt(gcd); i++) {
        if(gcd%i == 0) {
            devisor.push_back(i);
            if(i != gcd/i)
                devisor.push_back(gcd/i);
        }
    }
    sort(devisor.begin(), devisor.end());
    
    for(int i=1; i<devisor.size(); i++)
        cout << devisor[i] << ' ';
    
    return 0;
}

<유클리드 호제법(Euzlidean algorithm)>

https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법(Euclidean-algorithm)

 

<약수 구하는 방법>

https://kbw1101.tistory.com/32

[알고리즘] 효율적으로 약수를 찾는 알고리즘

 

<문제 바로가기>

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

2981번: 검문

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.