ラグランジュの四平方数再び
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の実行ファイルを出せるらしい。