백준 4690번 완전 세제곱 // C++

문제

 

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력

이 문제는 입력이 없다.

출력

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

 

---

 

풀이

 

단순하게 4중 for문을 이용하여 세 개의 수의 세제곱의 합이 다른 수의 세제곱이 되면 출력하면 된다.

 

제일 작은 a의 값은 6이므로 6부터 시작하면 되고, b, c, d는 오름차순으로 출력해야 하므로 더 큰 값부터 for문의 index를 시작하면 된다.

 

---

 

코드

#include <iostream>

using namespace std;

int power(int num) {
	return num * num * num;
}

int main() {
	for (int i = 6; i <= 100; i++) {
		for (int j = 2; j < i; j++) {
			for (int k = j + 1; k < i; k++) {
				for (int l = k + 1; l < i; l++) {
					if (power(i) == power(j) + power(k) + power(l)) {
						printf("Cube = %d, Triple = (%d,%d,%d)\n", i, j, k, l);
					}
				}
			}
		}
	}
}