취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25323번 문제인 수 정렬하기, 근데 이제 제곱수를 곁들인이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25323 

세 양의 정수 x, y, z가 있을 때, 어떤 x와 y의 곱이 제곱수이고 y와 z의 곱 또한 제곱수라면 (xy)(yz)(zx) = (xyz)^2와 같은 관계로부터 xz 또한 제곱수가 되야 함을 알 수 있다. 따라서, 주어진 수열의 각 원소 x를 정렬 후의 위치로 옮길 수 있는지의 여부는 그 위치에 처음에 있던 수 y와 x의 곱이 제곱수가 되는지의 여부와 같게 된다. 즉, 주어진 수열을 A, 정렬된 수열을 B라 할 때, 각 인덱스 i에 대하여 A[i]와 B[i]의 곱이 제곱수인지를 확인하는 것으로 문제를 해결할 수 있다.

양의 정수가 하나 있을 때 그 수가 제곱수인지는 이진탐색을 통해 빠르게 알아낼 수 있다. 이 방법을 이용해 수열의 두 원소 x와 y가 서로 교환가능한지를 판단하기 위해 두 수를 곱해 얻을 수 있는 수가 제곱수인지를 판단하고 싶지만, 주어지는 수의 크기가 최대 10^18까지 가능하므로 두 수를 직접 곱해 그 정수가 제곱수인지를 판단하는 것은 쉽지 않아보인다. 따라서 수의 크기를 키우지 않고 두 수의 곱이 제곱수가 되는지를 판단할 방법을 생각해볼 필요가 있다.

두 양의 정수 x와 y의 곱이 제곱수인지를 판단하는 것은 x/gcd(x,y)와 y/gcd(x,y)가 각각 제곱수인지를 판단하는 것과 동치임을 관찰하자. 이는 x=ag, y=bg (단, g=gcd(x,y))로 써두고 수식을 살짝 전개해보면 금방 얻을 수 있는 관계이다.

두 양의 정수 x와 y의 곱이 제곱수인지를 판단하는 또다른 방법으로 gcc의 __int128을 이용하는 방법이 있다. __int128은 gcc 컴파일러가 제공하는 128비트 정수 자료형으로, 이를 이용하면 입력으로 들어오는 두 정수를 직접 곱해도 오버플로우가 발생하지 않아 두 수를 곱해 얻은 수가 제곱수인지를 이진탐색으로 바로 판단할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int N;
ll arr[500000];
ll sortarr[500000];

bool is_square(ll x) {
	ll L = 1, R = 1000000000;
	while (L < R) {
		ll mid = (L + R) / 2;
		if (mid * mid < x) L = mid + 1;
		else R = mid;
	}
	return L * L == x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		ll& x = arr[i]; cin >> x;
		sortarr[i] = x;
	}

	sort(sortarr, sortarr + N);

	for (int i = 0; i < N; i++) {
		ll x = sortarr[i], y = arr[i];
		ll gcdxy = gcd(x, y);
		x /= gcdxy, y /= gcdxy;
		if (is_square(x) && is_square(y)) continue;
		cout << "NO";
		return 0;
	}

	cout << "YES";
}