알고리즘

세 거듭제곱 문제

path7inder 2014. 9. 24. 18:40
프로그램 명: cube
제한시간: 1 초

페르마의 마지막 정리 " 2 보다 큰 n 에대해서 , a^n = b^n + c^n 인 1 보다 큰 a , b , c 가 존재하지 않는다 "

몇 백년 동안 페르마의 마지막 정리는 증명되지 않았다. ( 최근에 이 정리가 증명되었지만 , 아직 더 엄밀한 검증이 필요하다)

우리가 관심있는 식은 다음 식이다.( b,c,d > 1)

a3 = b3 + c3 + d3

N 이 주어질 때 N 이하 인 a 로 등식을 만족하는 집합 {a,b,c,d} 를 모두 구하는 것이다.

입력

100 이하인 정수 N 이 주어진다.

출력

입출력 예의 형식으로 출력한다. a 가 작은 순으로 출력하고 a 가 같은 경우 b 가 작은 순으로 출력한다.

입출력 예

입력

24

출력

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

출처: Mid-Central USA 1995

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <math.h>
 
using namespace std;
 
void func(int num)
{
    int numThree = (int)(pow((double)num,3.0));
    int i,j,k;
    int min,mid,max;
 
    for(i=2; i<num; i++)
        for(j=i; j<num; j++)
            for(k=j; k<num; k++)
                if(numThree == (pow(i,3.0) + pow(j,3.0) + pow(k,3.0))){
                    printf("Cube = %d, Triple = (%d,%d,%d)\n",num,i,j,k); 
                    // 다 돌려보면 나옵니다.
                    break;
                }
}
 
int main()
{
    int N;
    
    cin>>N;
 
    for(int i=6; i<=N; i++){
        func(i);
    }
}

4 중첩 for문이지만... 그래도 4단계니까 괜찮을거에요...