지문, 최근 제출, 제출 폼을 준비하고 있습니다.
모든 값에서 을 빼서 처음 값을 로 바꾸어 생각하자. 라면 모든 값을 로 바꾸면 되므로, 이후에는 라고 가정한다.
, , , , 라고 하자. 최종 값은 반드시 전체 평균 이다. 연산을 몇 번 하더라도 모든 값은 기약분수로 나타냈을 때 분모가 의 거듭제곱수이므로, 가 의 거듭제곱수가 아니면 불가능하다.
가 의 거듭제곱수라고 하자. 이므로 이다. 라고 두면 최소 연산 횟수는 이다.
Construction
이면 는 홀수이다. 개의 그룹을 만들고, 각 그룹의 크기를 , 의 개수를 각각 로 둔다. 남은 원소는 개의 크기 인 그룹으로 나눈다.
Bound
한 번이라도 함께 연산한 두 인덱스 사이에 간선을 이어 그래프 를 만들고, 연결 요소의 개수를 라고 하자. 연결 요소의 크기가 라면 그 안의 최종 합 가 정수여야 하므로 는 의 배수이다. 각 연결 요소의 크기를 라고 하면 이다.
전체 시간 복잡도는 이다.
Solution written by GPT5.6
크기 인 그룹에 가 개 들어간다면 의 개수는 각각 , , 여야 한다. 따라서 이고, 모든 크기 인 그룹에서 의 합을 로 맞추면 된다. 의 정의로부터 항상 가능하다.
각 그룹은 정확히 그룹 크기에서 을 뺀 횟수만큼의 연산으로 평균화할 수 있다. 크기 인 그룹은 로 이루어지고 합이 홀수이다. 크기 인 그룹은 모든 값을 로 나누면 합이 홀수인 그룹이 된다.
크기가 이고 원소가 이며 합이 홀수 인 그룹을 생각하자. 연산을 거꾸로 구성한다. 처음에는 최종 평균 가 개 있다고 생각한다. 같은 값 두 개를 골라 하나를 원래 정수 로 확정하고, 다른 하나를 로 되돌리면 평균 연산 하나를 역으로 복원할 수 있다.
현재 활성 원소의 수가 일 때 라고 하자. 모든 활성 값의 소수 부분은 이므로 활성 값은 와 두 종류뿐이다. 높은 값의 개수를 라고 하고 같은 종류끼리 두 개씩 묶는다.
다음 단계의 활성 원소는 개이다. 각 상태 에서 앞으로 복원할 수 있는 남은 의 개수는 하나의 정수 구간을 이룬다. 에서는 또는 이고, 위 전이로 작은 부터 구간을 계산할 수 있다. 접두·접미 최솟값과 최댓값을 사용하면 한 레벨을 에 계산할 수 있고, 모든 레벨의 크기 합도 이다. 복원할 때는 다음 상태가 가능한 구간 안에 남는 전이를 하나 고른다. 기록한 역연산의 순서를 뒤집으면 번의 정방향 연산을 얻는다.
번째 연결 요소에 처음 가 개 있었다면 그 연결 요소의 합은 이므로 이다. 가 홀수이므로 다음이 성립한다.
따라서 이다. 한 연결 요소를 만들려면 적어도 그 크기에서 을 뺀 만큼의 연산이 필요하므로 전체 연산 수는 적어도
이다.
