4A. 펜윅국 선발고사 I (Team Selection IV)

문제

인덱스국 펜윅국 선발고사 : Day 4

인덱스국의 조교장이었던 앤디는 펜윅국에 납치되어 펜윅대학교(Fenwick University)의 컴퓨 터공학과 교수와 펜윅국 정보올림피아드(FOI)의 선발고사 출제를 담당하게 되었습니다. 하지만 앤디는 학생들이 모두 펜윅 트리만을 사용한다는 사실을 모른 채 RMQ 문제만 5개를 연달아 출제해 버렸고, 그 선발고사는 사상 최악의 구데기컵이 되고 맙니다.

펜윅국에서는 이 구데기컵에 책임을 느끼고, 획일화된 인재 양성에 치중된 FOI에서 2명의 학생이 짝을 지어 연구 과제를 수행하는 코드 페어 (Code Pair) 의 형태로 선발고사 방식을 바꿨습니다.

앤디는 BIT School(Baekjoon Informatics & Technology School) 학생들의 지도를 담당하게 되었습니다. 하지만 고국 땅이 그리웠던 앤디는 허송세월하다 연구 주제를 정하지 못했고, 마침 옆 학교에서 선인장 최대 매칭을 구하는 주제를 선택했다는 소문이 돌자 비슷한 그래프 문제를 학생들에게 던져주고, 야심한 밤 감시를 피해 달아나기로 했습니다.

앤디가 생각한 그래프는 이른바 'GCD 그래프'로, 총 V개의 정점을 가집니다. $i$ 번 정점에는 양의 정수 $A_i$ 가 쓰여 있고, 두 정점 $i$ , $j$ 는 $gcd(A_i, A_j) \neq 1$ 일 때만 간선으로 연결되어 있다고 합니다. (0 ≤ $i$ ≤ V − 1) 열심히 이 그래프를 가지고 고민한 앤디는 에지가 정확히 E개인 'GCD 그래프'를 가능한 한 가장 작은 $A_i$ 들을 이용하여 구성하는 문제를 생각해냈습니다. 앤디의 지도학생인 아거스는 어처구니 없는 난이도의 과제에 당황하여, 순식간에 이 문제를 해결해버리고 달아나려는 앤디를 붙잡아 여행가방을 불태워버렸습니다. 아거스의 팀원인 당신도 빨리 이 문제를 해결하고 앤디를 펜윅국 정부로 호송하도록 합시다.

구현 세부 사항

다음 함수들을 구현하시오.

int[] gcdGraph(int E)

이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
이 함수는 간선이 정확히 E개가 되는 GCD graph를 만들어 R[i] = $A_i$ 인 크기 V의 배열을 반환해야 합니다.

제한 조건

1 ≤ E ≤ $10^8$
1 ≤ $A_i$ ≤ $10^6$ 을 만족해야 합니다.

부분 점수

이 문제는 부분 점수 문제입니다. 여러분이 구성한 그래프의 $max A_i$ 에 따라 점수가 달라집니다.

V > 50,000일 경우 0점을 받습니다.
여러분의 그래프가 제한 조건 중 만족하지 않는 것이 있을 경우 0점을 받습니다.
그래프가 제한 조건을 모두 만족할 경우, 만든 그래프의 $max A_i$ 를 $A_O$ , 출제자가 만든 그래프의 $max A_i$ 를 $A_C$ 라고 한다면 여러분의 점수는 (해당 테스트 케이스의 만점) × $\min(1, (A_C / A_O)^{0.5})$ 점을 소수점 첫째 자리에서 반올림한 값입니다.

예제 입출력

E = 4

그레이더는 다음 함수를 호출합니다.

gcdGraph(4)

그레이더가 반환할 수 있는 올바른 값의 예시는 다음과 같습니다. 이 답은 만점 답안이 아님에 유의하세요.

R = [6, 15, 35, 77]

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

line 1 : E