AOJ1241 Lagrange's Four-Square Theorem

問題リンク Lagrange's Four-Square Theorem

• 概要

ラグランジュの4平方の定理は、全ての自然数は4つの平方数の和で表せるというものである。整数Nが与えられるので、Nを4つの平方数の和による表し方は何通りあるかを答えよ。
N < 2^15

• 解法

4重for文+枝刈りで何とか間に合います。

• ソース

import java.util.Scanner;

//Lagrange's Four-Square Theorem
public class AOJ1241 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			int c = 0;
			for(int i=0;i<=n;i++){
				if(n<i*i)break;
				for(int j=i;j<=n;j++){
					if(n<i*i+j*j)break;
					for(int k=j;k<=n;k++){
						if(n<i*i+j*j+k*k)break;
						for(int l=k;l<=n;l++){
							if(n<i*i+j*j+k*k+l*l)break;
							c+=i*i+j*j+k*k+l*l==n?1:0;
						}
					}
				}
			}
			System.out.println(c);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1241().run();
	}
}