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) | ↑ページトップ |