(C++) - 백준(BOJ) 2981번 : 검문

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

2981번: 검문

gcd구한 후 약수를 구하는 문제였습니다.

 

 

풀이방법

 1. gcd 구하기 : 나누어 나머지가 같은 m의 의미는 각 수의 차이들에 대해 최대공약수를 찾는 다면 이들의 약수가 모두 m이 된다는 뜻입니다.

 

 2. 약수 구하기 : i * i <= m가 되는 i의 범위 내에서 약수를 구해줍니다. m % i가 0이 된다면 i와 m/i모두 정답이 됩니다. i*i=m의 경우에는 i가 겹쳐 들어갈 수 있으므로 set에 넣어줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, m;
int num[101];
set <int> numSets;
int gcd(int a, int b){
    if(!b) return a;
    return gcd(b,a%b);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> num[i];
    for(int i = 1; i < n; i++) m = gcd(abs(num[i] - num[i-1]),m);
    for(int i = 1; i <= sqrt(m); i++){
        if(m % i == 0){
            numSets.insert(i);
            numSets.insert(m/i);
        }
    }
    for(auto n : numSets) if(n != 1) cout << n << ' ';
}