취미로 코딩하기

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

이번에 볼 문제는 백준 23128번 문제인 Math이다.
문제는 아래 링크를 확인하자.

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

먼저 다음과 같은 사전지식을 상기하자:
\(O(\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}) = O(n\lg n)\) (조화급수 형태로 나타나는 알고리즘의 시간복잡도 계산)

두 양의 정수 \(a\), \(b\)에 대하여 어떤 양의 정수 \(c\)가 존재해 \(a^2+b=c^2\)가 성립한다면 이는 곧 \(b = (c-a)(c+a)\)가 성립한다는 것을 의미한다. 따라서 주어진 \(n\) 이하의 각 정수 \(a_j\)에 대하여 위와 같은 형태로 분해할 수 있는지를 판단하는 것으로 문제를 해결할 수 있다.

한편 위의 사전지식에 의하여, 1 이상 100만 이하의 각 정수 \(k\)에 대해 모든 100만 이하의 \(k\)의 배수마다 (해당 수를 \(k\)로 나눈 수)와 \(k\) 각 수를 쪼개는 시도를 반복하는 것은 제한시간 내에 충분히 해낼 수 있음을 알 수 있다. 이를 활용해 \(b\)를 쪼갤 수 있는 모든 방법을 직접 시도해 문제의 답을 구하자.

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

#include <iostream>
using namespace std;

int N;
bool A[1000001];
int ans;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		A[x] = 1;
	}

	for (int i = 1; i < 1000001; i++) {
		for (int j = i; j < 1000001; j += i) {
			if (!A[j]) continue;
			int AA = i, BB = j / i;
			if (AA > BB) continue;
			int K = BB - AA;
			if (K & 1) continue;
			K >>= 1;
			if (A[K] && K != j) ans++;
		}
	}

	cout << ans;
}