Teorema dei quattro quadrati

Luca sta ripassando matematica in vista dell’esame di maturità e in particolare sta studiando il teorema di Lagrange relativo alle funzioni continue e derivabili.
Incuriosito dal lavoro del matematico italiano è andato a cercare quali altri teoremi gli vengono attribuiti e ne ha trovato uno interessante.
Il teorema in questione è detto Teorema dei quattro quadrati e afferma che ogni intero positivo può essere espresso come somma di (al più) quattro quadrati perfetti.

Formalmente:

n = a²+b²+c²+d² ∀n∈ℕ

dove a, b, c, d sono interi non negativi.

Luca però non riesce a trovare un modo per sapere in quanti modi diversi n può essere ottenuto seguendo quanto afferma il teorema.
Aiuta Luca!

Dati di input

Il file input.txt è composto da due righe.

• La prima riga contiene l’intero N.
• La seconda riga contiene N interi separati da uno spazio, i numeri V_i su cui applicare il teorema.

Dati di output

Il file output.txt è composto da un’unica riga contenente N interi: l’i-esimo numero indica in quanti modi diversi si può ottenere V_i seguendo il teorema.

Assunzioni

• 1 ≤ N ≤ 200.
• 1 ≤ V_i ≤ 2¹⁵ per ogni i=0…N−1.

Esempi di input/output

input.txt	output.txt
1 25	3
2 10 31	2 2

Spiegazione

Nel primo caso di esempio, 25 si può ottenere con le tre seguenti combinazioni:

1. 25 = 1²+2²+2²+4²
2. 25 = 3²+4² (+0²+0²)
3. 25 = 5² (+0²+0²+0²)

---

/*
	www.valcon.it
	ABC - Teorema dei quattro quadrati
*/
#include
#include
#include

using namespace std;

int       	N;
long long 	V,
			A,VA,minA,maxA,
			B,VB,minB,maxB,
			C,VC,minC,maxC,
			D;
int       	contatore;		  

void elabora()
{
	contatore=0;			
	maxA=sqrt(V);
	minA=sqrt(V/4);
	for(A=maxA; A >= minA; A--)
	{
		VA=V-A*A;		
		maxB=sqrt(VA);
		maxB=min(maxB,A);
		minB=sqrt(VA/3);
		for(B=maxB; B >= minB; B--)
		{
			VB=VA-B*B;	
			maxC=sqrt(VB);	
			maxC=min(maxC,B);
			minC=sqrt(VB/2);
			for(C=maxC; C >= minC; C--)
			{
				VC=VB-C*C;	
				D=sqrt(VC);	
				D=min(D,C);
				if(VC-D*D == 0)	contatore++;								
			}
		}
	}
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");

	fin >> N;							// quanti numeri
	
	for(int i=1; i <=N; i++)			// per ogni numero
	{
		fin >> V;						// input
		elabora();						// elaborazione
		fout << contatore << ' ';		// output
	}
	
	return 0;
}