ラグランジュの四平方数再び

id:zyxwv:20070604 の言う通りです。
上限からだけじゃなく、下限からの探索打ち切りができる。これに一瞬で気づける人がICPC行くんだろう。

#include <stdio.h>
#include <math.h>

int cmp (int a, int b, int c, int d, int n)
{
  int s = a * a + b * b + c * c + d * d;
  if (n == s) return 0;
  if (n < s) return 1;
  return -1;
}

int main (int argc, char **argv)
{
  int count = 0;
  int i,j,k,l;
  int n = 20007;
  for (i = (int) sqrt (n); i >= 0; i--) {
    if (cmp (i,0,0,0,n) == 1) continue;
    if (cmp (i,i,i,i,n) == -1) continue;
    for (j = i; j >= 0; j--) {
      if (cmp (i,j,0,0,n) == 1) continue;
      if (cmp (i,j,j,j,n) == -1) continue;
      for (k = j; k >= 0; k--) {
	if (cmp (i,j,k,0,n) == 1) continue;
	if (cmp (i,j,k,k,n) == -1) continue;
	for (l = k; l >= 0; l--) {
	  if (cmp (i,j,k,l,n) == 0) count++;
	}
      }
    }
  }
  printf("%d\n", count);
  return 0;
}

time ./a.out
738

real    0m0.034s
user    0m0.033s
sys     0m0.001s

おー。

• Dr.Schemeを試してます。

気になっていたFrTimeに触ったり(Functional Reactive Programming) ググったらk.inaba氏の言及を発見、Open Source Cross Platform な GUIで遊んだり。WinとMacOSXとLinuxの実行ファイルを出せるらしい。