https://www.acmicpc.net/problem/14476
[문제]
정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다.
최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다.
N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것을 찾는 프로그램을 작성하시오. 이때, 최대공약수는 K의 약수가 되면 안 된다.
예를 들어, 정수 8, 12, 24, 36, 48에서 8을 빼면 나머지 12, 24, 36, 48의 최대공약수는 12가 되고, 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. 이때, 다른 수를 빼도 최대공약수가 8보다 커질 수 없다.
하지만, 8, 12, 20, 32, 36의 경우에는 그 무엇을 빼더라도 나머지 수의 최대공약수가 K의 약수가 되기 때문에, 정답을 구할 수 없다.
N개의 수가 주어졌을 때, 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다.
[출력]
첫째 줄에 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 출력하고, 공백을 출력한 다음 뺀 수를 출력한다.
뺀 수를 K라고 했을 때, 나머지 수의 최대공약수가 K의 약수가 되면 안 된다.
만약 정답이 없는 경우에는 -1을 출력한다.
[예제 입력1]
5
8 12 24 36 48
[예제 출력1]
12 8
[단서]
- 최대공약수 -> gcd 알고리즘
- N = 10^6
- 누적합 알고리즘
[해결]
-
왼쪽 -> 오른쪽으로 누적해서 gcd를 구하는 ltr배열 생성
-
오른쪽 -> 왼쪽으로 누적해서 gcd를 구하는 rtl배열 생성
-
0부터 n-1까지 순회를 하면서, index가 뺄 수 K의 인덱스라고 하자.
3-1. 맨왼쪽수인 경우 rtl[1]이 맨왼쪽수를 제외한 배열의 최대공약수
3-2. 맨오른쪽수인 경우 ltr[n-2]이 맨오른쪽수를 제외한 배열의 최대공약수
3-3. 나머지는 ltr[i-1]과 rtl[i+1] 간 최대공약수 끼리의 최대공약수를 통해 계산 -
만약 구한 최대공약수가 k의 약수인경우, pass
-
만약 구한 최대공약수가 k의 약수가 아니면, 큰 최대공약수 처리
처음에는 "누적 합"에 집중을해서 접근을 했지만,
누적 "합"의 의미가 아니라 "누적" 합의 의미를 가진 문제라고 볼 수 있다.
즉, 기존까지의 누적합은 실제 값을 누적해서 더하는 배열을 의미하는 것이었지만 누적해서 계산한 값 (이 문제의 경우 gcd) 을 저장한다 라고 생각을 해볼 수 있는 문제였다.
[코드]
#include <stdio.h>
#include <stdlib.h>
int n, max_gcd, max_index;
int arr[1000001];
int ltr[1000001];
int rtl[1000001];
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a%b);
}
int main()
{
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%d",&arr[i]);
}
ltr[0] = arr[0];
for(int i=1; i<n; i++) {
ltr[i] = gcd(ltr[i-1], arr[i]);
}
rtl[n-1] = arr[n-1];
for(int i=n-2; i>=0; i--) {
rtl[i] = gcd(rtl[i+1], arr[i]);
}
max_gcd = 0;
max_index = -1;
for(int i=0; i<n; i++) {
int k = arr[i];
if(i == 0) {
if(k % rtl[1] != 0) {
if(max_gcd < rtl[1]) {
max_gcd = rtl[1];
max_index = 0;
}
}
}
else if(i == n-1) {
if(k % ltr[n-2] != 0) {
if(max_gcd < ltr[n-2]) {
max_gcd = ltr[n-2];
max_index = n-1;
}
}
}
else {
int m = gcd(ltr[i-1], rtl[i+1]);
if(k % m != 0) {
if(max_gcd < m) {
max_gcd = m;
max_index = i;
}
}
}
}
if(max_index != -1) {
printf("%d %d",max_gcd, arr[max_index]);
}
else {
printf("-1");
}
return 0;
}