[SWEA] 준홍이의 네 개의 제곱수

Posted on | In |

문제 보러가기

제한사항

자연수 N(1 ≤ N ≤ 32767)이 하나 주어진다.

첫번째 생각

라그랑주의 네제곱수 정리(Four Square Theorem)를 참고하여 코드를 작성하였다.

참고링크 : https://jjycjnmath.tistory.com/295

Code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int count = 0;
			int num = sc.nextInt();
			if (num == 0)
				break;
				int len = (int) Math.sqrt(num);
				for (int i = 1; i <= len; i++) {
					if (i * i == num) {
						count++;
						continue;
					}
					for (int j = i; j <= len; j++) {
						if (i * i + j * j == num) {
							count++;
							break;
						} else if (i * i + j * j > num)
							break;
						for (int k = j; k <= len; k++) {
							if (i * i + j * j + k * k == num) {
								count++;
								break;
							} else if (i * i + j * j + k * k > num)
								break;
							for (int l = k; l <= len; l++) {
								if (i * i + j * j + k * k + l * l == num) {
									count++;
									break;
								} else if (i * i + j * j + k * k + l * l > num)
									break;
							}
						}
					}
				}
				System.out.println("#"+tc+" "+count);
			}
		}
	}