PKU 2042 AOJ 1241 Lagrange's Four-Square Theorem
http://poj.org/problem?id=2042
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1241
ある整数が4個以下の整数の二乗の和で表されるとき、その組み合わせの個数を答えるもの。しばらくぶりにAOJを解いたような気がします。
事前に出てくる数の答えを計算して、それを出力。
200^4に近いきがしましたが、枝刈りでがりがり削れるっぽいです。
int sq[200]; int ans[33001]; int n; main(){ rep(i,200)sq[i]=i*i; for(int i=1;i<200;i++){ int ti=sq[i]; if(ti>33000)break; ans[ti]++; for(int j=i;j<200;j++){ int tj=ti+sq[j]; if(tj>33000)break; ans[tj]++; for(int k=j;k<200;k++){ int tk=tj+sq[k]; if(tk>33000)break; ans[tk]++; for(int l=k;l<200;l++){ int tl=tk+sq[l]; if(tl>33000)break; ans[tl]++; } } } } while(cin>>n,n){ cout<<ans[n]<<endl; } }