백준 2981번

2981번 검문 문제입니다.

문제 이름과 상관없이 n개의 자연수를 나눴을 때 일정한 값이 나오는 i(2개 이상이 될수 있음)을 찾는 문제입니다.

상황을 수식으로 표현하면 i번째 자연수 A[i]를 나머지가 j인 임의의 정수 m으로 나눴을때의 A[i]는 임의의 정수 k[i] * m + j라고 표현할 수 있습니다.

변수 m이 우리가 구하고자 하는 값이므로, j를 없애기 위해 A[i]와 A[i-1]을 계산해봅니다.

A[i] - A[i-1] = m * (k[i] - k[i-1]) 으로 정리할 수 있습니다.

이제 m을 구하기 위해서 i번째와 i-1번째 자연수 값의 차이를 구하고, 그 과정에서 등장하는 최대공약수와 그의 약수들을 구하면 됩니다.

컴퓨터공학을 위해 수학을 배워야 하는 이유가 꾸준히 나타나는 것 같습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
 
int gcd(int a, int b) {
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
int main() {
    int n;
    scanf("%d", &n);
    int* numArr = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &numArr[i]);
    }
    std::sort(numArr, numArr + n);
 
    int gap = numArr[1] - numArr[0];
    for (int i = 1; i < n - 1; i++) {
        gap = gcd(gap, numArr[i + 1] - numArr[i]);
    }
 
    std::vector<int> printArr;
    for (int i = 2; i * i <= gap; i++) {
        if (gap%i == 0) {
            printArr.push_back(i);
            if (i*i < gap) {
                printArr.push_back(gap / i);
            }
        }
    }
    printArr.push_back(gap);
 
    std::sort(printArr.begin(), printArr.end());
    for (std::vector<int>::iterator iter = printArr.begin(); iter != printArr.end();iter++) {
        printf("%d ", *iter);
    }
}