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; }