[PS] 수 정렬하기, 근데 이제 제곱수를 곁들인 / C++ (백준 25323번)

2022년 UCPC 예선 J번 문제로, 문제를 처음 읽고 나서 STL sort에 cmp 함수 만들어서 제약을 걸어주면 되는 거 아닌가?라는 생각에 쉽게 풀릴 것 같았지만 제약이 생각대로 걸리지 않았고, 다음과 같은 방법으로 해결했다.

 

해결 방법 (에드혹)

 원래 배열을 정렬이 끝난 배열과 비교하는 과정에서 A(정렬 전 배열의 i번째에 있던 값)와 B(정렬 후 배열의 i번째에 있는 값)가 있다고 가정하자.

1. A = B라면 위치가 변하지 않은 것으로 확인할 게 없이 넘어가면 된다.
2. A ≠ B라면 B의 정렬 전 위치에 있던 수가 C라고 하자. C = A라면 A와 B의 위치가 바뀐 것이므로  A x B가 제곱수인지 확인하면 된다. 하지만 C가 A가 아니라면?
3. A, B, C 모두가 다른 것은 A ↔ B, B ↔ C 이런 식으로 교환이 이뤄졌을 것이다. 이 때 D, E, F.. 등 더 복잡한 교환이 추가로 이뤄질 수도 있다. 
   • 하지만 이 때 A ↔ B, B ↔ C가 교환이 됐다는 것은 A ↔ C가 성립한다는 것과 같다. 중간에 복잡한 교환이 추가로 있어도 각자 교환이 모두 성립한다면, A ↔ C는 성립한다. 결과적으로 모든 i에 대해 (정렬 전 i에 위치한 값 ↔ 정렬 후 i에 위치한 값)이 성립한다면 모든 교환을 해보지 않아도 가능하다는 것을 알 수 있다.

 

두 수의 곱이 제곱수인지 확인

•  정수로 들어올 수 있는 값이 1~10^18이므로 long long int로 받기만 가능하며 곱할 수는 없다. 이때, 두 수의 곱이 제곱수인지 확인하는 방법은 양 수의 최대공약수를 구하여 나눈 값이 제곱수인지 확인하면 된다.

증명) AB가 제곱수인지 확인할 때 최대공약수를 C라고 하면, AB=abCC이며 C가 2번 곱해졌으므로 a와 b가 제곱수인지만 확인하면 된다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll d[500001];
pair<ll, ll> match[500001];

ll gcdd(ll a, ll b) {
    if (b == 0) return a;
    return gcdd(b, a % b);
}


bool isPerfectSquare(ll x) {
    ll s = (ll)(sqrt(x) + 0.5);
    return s * s == x;
}

bool cmp(ll a, ll b) {
    ll g = gcdd(a, b);
    ll aDiv = a / g;
    ll bDiv = b / g;
    if (isPerfectSquare(aDiv) && isPerfectSquare(bDiv))
        return true;
    return false;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &d[i]);
        match[i].first = d[i];
        match[i].second = i;
    }
    sort(match, match + n);
    
    for (int i = 0; i < n; i++) {
        if (match[i].second != i) {
            if (!cmp(match[match[i].second].first, match[i].first)) {
                printf("NO\n");
                return 0;
            }
        }
    }
    printf("YES\n");
    return 0;
}