31215번 - 이상한 섞기 연산 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1002 | 498 | 424 | 51.961% |
문제
인덱스가 $1$부터 시작하는 길이 $n$의 수열 $B$가 있으며, 초기에 모든 인덱스 $k$에 대해 $B_k=k$입니다. 흐즈로는 이 수열에 할 수 있는 매우 이상하고 신기한 연산을 생각해 냈습니다. 그 연산은 다음과 같습니다.
- 어떠한 양의 정수 $k$가 주어질 때, $k$의 약수인 가장 큰 $2$의 거듭제곱수 $l$을 찾고, $k \neq l$이라면 $B_k$와 $B_l$을 서로 교환하는 동작을 $k$-교환이라고 합시다.
- $i$-교환을 $i=1,2,\cdots,n$에 대해 순서대로 반복합니다.
흐즈로는 이 연산을 이상한 섞기 연산이라고 부르기로 했습니다. 수열 $B$의 길이 $n$이 주어질 때, $B$에 이상한 섞기 연산을 수행한 뒤 원소 $1$이 있는 인덱스를 출력하세요. 다시 말해, 연산이 끝난 후 $B_j=1$이 되는 인덱스 $j$를 찾아 출력해야 합니다.
입력
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 1000$)
그다음 줄부터 총 $T$개의 줄에 각각 $B$의 길이를 나타내는 정수 $n$이 한 줄에 하나씩 주어집니다. ($1 \le n \le 10^9$)
출력
각 테스트 케이스에 대해, 길이가 $n$인 수열 $B$에 이상한 섞기 연산을 수행한 뒤 원소 $1$이 있는 인덱스 $j$를 별도의 줄에 출력하세요.
예제 입력 1
2 1 3
예제 출력 1
1 3
$n=1$일 때, $1$이 존재할 수 있는 위치는 $1$번째가 유일합니다. 따라서 정답은 $1$입니다.
$n=3$일 때, 이상한 섞기 연산이 끝난 후 $B$는 $[3,2,1]$이 됩니다. 이때 $1$은 $3$번째 인덱스에 존재합니다. 따라서 정답은 $3$입니다.
노트
본 문제에서 $2$의 거듭제곱수는 $2^k$ 꼴로 표현했을 때 $k$가 음이 아닌 정수가 되는 수로 정의됩니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호