문제
트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.
상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.
먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.
N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.
입력
첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)
다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.
항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.
출력
첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.
풀이
넘 어려운 수학 문제..
각 수를 arr[i]라 하자. 모든 arr[i]를 M으로 나눴을 때, 나머지가 r로 모두 같아져야 한다. 식으로 나타내면
arr[1] = q1 * M + r
arr[2] = q2 * M + r
arr[3] = q3 * M + r ... 각 항을 빼면
arr[1] - arr[2] = M * (q1 - q2)
arr[2] - arr[3] = M * (q2 - q3) ...-> M으로 나눴을 때 나머지가 같은 각 항에서, M은 각 항의 차의 약수이다.
따라서, 모든 M을 구하려면, 나머지가 같은 각 항의 차의 최대공약수의 1을 제외한 약수를 구하면 된다.
모든 수의 차의 최대공약수를 구하기 위해서, 최대공약수를 구하는 알고리즘을 알아야 한다.
두 수의 최대공약수는 유클리드 호제법을 사용해서 구할 수 있다.
두 양의 정수 a, b(a > b)에 대하여, a = b * q + r (0 <= r < b)이라 하면,
a, b의 최대공약수는 b, r의 최대공약수와 같다.
r = 0이라면, a, b의 최대공약수는 b이다.이 알고리즘을 이용하여 a, b의 최대공약수를 구하려면, 재귀를 이용하여 r = 0이 될 때까지 반복하면 된다.
a = b * q1 + r1
b = r1 * q2 + r2
r1 = r2 * q3 + r3
r2 = r3 * q4 + 0위의 예시의 4번째 식에서, r = 0 이므로, gcd(r2, r3) = r3 이다.
3번째 식에서, gcd(r1, r2) = gcd(r2, r3) = r3 이다.
2번째 식에서, gcd(b, r1) = gcd(r1, r2) = r3 이다.
1번째 식에서, gcd(a, b) = gcd(b, r1) = r3 이다.
따라서,
a = b / q + r에서, r = 0일 때 까지 재귀를 반복하면 된다.
위의 과정으로 arr[1], arr[2] 두 수의 최대공약수를 구했다. 1 ~ n까지의 수의 최대공약수를 구해야 하므로,
arr[1] - arr[2],
arr[2] - arr[3]...
arr[n - 1] - arr[n] 까지, n - 1번 이 과정을 반복하여 모든 수의 최대공약수를 구한다.
문제에서 원하는 것은 모든 수의 약수를 구하는 것이므로, 모든 수의 최대공약수의 약수를 구하여, 정렬한 후 출력한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void input(void);
void find_gcd(void);
int gcd(int a, int b);
int arr[100], difference[99], n;
vector<int> output;
int main(void)
{
input();
find_gcd();
return (0);
}
void input(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
int i = -1;
while (++i < n)
cin >> arr[i];
sort(arr, arr + n, greater<>());
i = -1;
while (++i < n - 1)
difference[i] = arr[i] - arr[i + 1];
return ;
}
void find_gcd(void)
{
int result = gcd(difference[0], difference[1]);
int i = 1;
while (++i < n - 1)
result = gcd(difference[i], result);
i = 1;
while ((++i) * i <= result)
{
if (result % i == 0)
{
output.push_back(i);
output.push_back(result / i);
}
}
if (output.size() >= 2 && output[output.size() - 1] == output[output.size() - 2])
output.pop_back();
output.push_back(result);
sort(output.begin(), output.end());
i = -1;
while (++i < output.size())
cout << output[i] << ' ';
return ;
}
int gcd(int a, int b)
{
if (b == 0)
return (a);
else
return (gcd(b, a % b));
}
성공 !
