[백준] 25323. 수 정렬하기, 근데 이제 제곱수를 곁들인

newbieski·2022년 8월 30일

백준

목록 보기

165/210

언뜻 생각하기에 quick sort + 교환할때 제약을 적용하면 되겠다 생각할 수 있으나 {7, 7, 3, 7, 27} 같이 꼭 quick sort로는 안되지만 교환으로 정렬이 가능함
숫자가 최종 가야할 위치는 정렬을 한 번 하면 알 수 있음
A라는 숫자가 최종 가야할 위치에 B라는 숫자가 있어 (A, B) 교환이 발생하는 경우에
- 둘을 바로 교환
- B -> C로 교환된 상태에서 (A, C) 교환
- A -> D로 교환된 상태에서 (A, B) 교환 => 이 경우는 결국 (A, B) 교환이라 다른점이 없음
즉 (A, B)가 가능하거나 (B, C), (A, C)가 가능한지 확인을 하면 됨
그런데 여기서 (A, B)가 가능하고 (B, C)가 교환 가능할때 -> (A, C)가 안될 수 있을까?
- (A, B) => B가 홀수개로 갖고 있는 소수를 A가 홀수개로 갖고 있음 && 짝수개의 소수
- (B, C) => B가 홀수개로 갖고 있는 소수를 C가 홀수개로 갖고 있음 && 짝수개의 소수
- (A, C) => B의 홀수개, 짝수개, B의 홀수개, 짝수개 => 짝수개
즉 A, B가 가능한지만 보면 됨
정리하면 정렬하고, 가야할 위치의 값과 교환이 가능한지 판단하면 됨

곱해서 제곱근인지 판단하면 되는데, 숫자가 10^18임
python + math.sqrt를 사용했는데 큰 숫자에 대해서 값이 정확하지 않음
이분탐색으로 제곱근 구하고 판단
찾아보니 isqrt를 사용한다고 함
gcd의 성질을 이용해도 됨
- A, B가 있을때 공통으로 있는 소수가 있을 것임 => g
- A, B에서 공통으로 있는 소수를 제거하고 나온 숫자는 일단 제곱이어야함
- 공통으로 있는 소수는 양쪽에 다 있으므로 제곱
- A = gP, B = gQ 일때 ${AB=g^2 PQ}$ P, Q가 각각 제곱인지 보면 됨