読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

AOJ 1241 Lagrange's Four-Square Theorem

問題

与えられたNの値を4個以下の正の整数の二乗で表せる組み合わせの数を考える。

解法

全探索で全通り試した。(計算量考えるの苦手です)
とりあえず全探索で通って良かった。

ソースコード

#include<iostream>
using namespace std;

int main()
{
	int n;
	while (cin >> n && n != 0)
	{
		int ans = 0;
		for (int i = 1; i * i <= n; i++)
		{
			int sumI = i * i;
			if (sumI == n)ans++;
			for (int j = i; j * j <= n; j++)
			{
				int sumJ = sumI + j * j;
				if (sumJ == n)ans++;
				for (int k = j; k * k <= n; k++)
				{
					int sumK = sumJ + k * k;
					if (sumK == n)ans++;
					for (int l = k; l * l <= n; l++)
					{
						int sumL = sumK + l * l;
						if (sumL == n)
						{
							ans++;
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}