StepByStep #lagrange

[hwangnk1004]

• 문제 http://59.23.150.58/30stair/lagrange/lagrange.php?pname=lagrange

  • 양의 정수는 많아야 4 개의 제곱수의 합으로 표현가능하다는 것이 1770 년에 Joseph-Louis Lagrange 에 의해서 처음 발표되었다. 이는 Lagrange's Four-Square 이론으로 얄려져 있다. 우리가 관심있는 것은 양의 정수가 주어질 때 제곱수의 합으로 만들수 있는 종류가 몇 개가 되는 지를 구하는 것이 문제이다. 제곱수는 최대 4 개까지 사용가능한다. 단, 42 + 32 과 32 + 42 은 같은 표현으로 본다. 예를 들어 , n 이 25 인 경우 3 가지 표현이 가능한다. 12 + 22 + 22 + 42 32 + 42 52 물론 0 이 되는 답은 없다.

• 답

import java.util.Scanner;

public class Main { public static void main(String args[]) {

    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    int count = 0;

    for (long a = 0; a * a <= n; a++) {
        long a2 = a * a;
        if (a2 > n) {
            break;
        }
        for (long b = a; b * b <= n; b++) {
            long b2 = b * b;
            if (b2 > n) {
                break;
            }
            for (long c = b; c * c <= n; c++) {
                long c2 = c * c;
                long d2 = (int)Math.sqrt(n - (a2 + b2 + c2));

                if (c2 > n) {
                    break;
                }

                if (a2 + b2 + c2 + d2 * d2 == n && d2 >= 0 && d2 <= (int) Math.sqrt(n)) {
                    if (a <= b && b <= c && c <= d2) {
                        count++;
                    }
                }

            }
        }
    }
    System.out.println(count);

}

}