BOJ 34967 최대공약수 완충재

문제 링크입니다.

문제 요약

$10^8$을 넘지 않는 양의 정수 $N$개를 인접한 두 수의 최대공약수가 모두 다르도록 나열하세요.

풀이

방법은 여러 가지가 있습니다. 제 방법은 다음과 같습니다.

$3 \times 5, 5 \times 7, 7 \times 9, \cdots$의 인접한 수들의 최대공약수는 $5, 7, 9, \cdots$와 같이 서로 다른 값으로 나타납니다. 단순 나열로는 값이 너무 커지니 홀수들을 (큰 거 × 작은 거) 꼴로 배치합니다.

같은 수를 두 번 반복해서 쓰면 길이를 두 배로 늘릴 수 있습니다. 가장 작은 수가 3MAX라서 괜찮습니다.

여기다가 2를 곱하면 gcd가 전부 두 배가 된 똑같은 수열을 얻을 수 있습니다. MAX를 gcd로 갖도록 뒤집어서 붙이면 완성입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> even, odd;
 
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	for(int i = 3, j = 14001; i != j; ){
		even.push_back(2*i*j);
		even.push_back(2*i*j);
		odd.push_back(i*j);
		odd.push_back(i*j);
		if(i+j == 14004) j -= 2; else i += 2;
	}
	even.pop_back(); odd.pop_back(); reverse(odd.begin(), odd.end()); even.insert(even.end(), odd.begin(), odd.end());
	int n; cin >> n; for(int i = 0; i < n; i++) cout << even[i] << ' ';
}