Lagrange's Four-Square Theorem

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem B

[解説]

総当り、または動的計画法。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 using namespace std;
003 #define MAX 32768
004 
005 int T[MAX+1];
006 
007 main(){
008     for ( int i = 1; i <= MAX; i++ ) T[i] = 0;
009     for ( int i = 0; i*i <= MAX; i++ ) {
010         for ( int j = i; i*i + j*j <= MAX; j++ ) {
011             for ( int k = j; i*i+j*j+k*k <= MAX; k++ ){
012                 for ( int l = k; i*i+j*j+k*k+l*l <= MAX; l++ ){
013                     T[i*i + j*j + k*k + l*l]++;
014                 }
015             }
016         }
017     }
018     
019     int n;
020     
021     while (1){
022         cin >> n;
023         if ( n == 0 ) break;
024         cout << T[n] << endl;
025     }
026 }