# [Gold V] 라그랑주의 네 제곱수 정리 [문제 링크](https://www.acmicpc.net/problem/3933) ## 문제 설명 <p>양의 정수는 많아야 4개의 제곱수로 표현할 수 있다고 한다. 이 이론을 <a href="http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem">라그랑주의 네 제곱수 정리</a>라고 한다. 이 정리는 조제프루이 라그랑주가 1770년에 증명했다.</p> <p>우리는 이 이론을 증명하거나 새로운 이론을 발견할 필요는 없고, n이 주어졌을 때 4개 이하의 양의 제곱수의 합으로 n을 만들 수 있는 경우의 수를 구하려고 한다. 경우의 수를 구할 때 제곱수의 순서가 바뀌는 경우는 같은 경우로 본다. 따라서 3² + 4² 과 4² + 3²는 같은 경우이다.</p> <p>N이 25일 때 4개 이하의 제곱수의 합으로 표현 할 수 있는 경우는 1² + 2² + 2² + 4², 3² + 4², 5² 이렇게 3가지이다.</p> ## 입력 <p>입력은 최대 255줄이다. 각 줄에는 2¹⁵보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다.</p> ## 출력 <p>각 테스트 케이스에 대해서 입력으로 주어진 n을 많아야 4개의 제곱수로 나타내는 경우의 수를 출력한다.</p> ## 풀이 가지치기되어 $O(N^2)$보단 연산 수가 많이 적어서 4중 for문이 시간 안에 돕니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); while(true) { int n; cin >> n; if(!n) break; int cnt=0; for(int i=1;i*i<=n;i++) { int a=i*i; if(a==n) cnt++; for(int j=i;a+j*j<=n;j++) { int b=a+j*j; if(b==n) cnt++; for(int k=j;b+k*k<=n;k++) { int c=b+k*k; if(c==n) cnt++; for(int l=k;c+l*l<=n;l++) { int d=c+l*l; if(d==n) cnt++; } } } } cout << cnt << '\n'; } } ```