fc2ブログ



Lagrange's Four-Square Theorem

2007.08.23 12:50  ACM/ICPC 2003

[問題] 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 }
スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ