Time Lapse :1hour 1min 3sec
7103.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| #include <stdio.h> #define MAXN 32767 int DP[MAXN+1]; int scan_d() { int ip=getchar_unlocked(),ret=0,flag=1; for(;ip<'0'||ip>'9';ip=getchar_unlocked()) if(ip=='-'){ flag=-1; ip=getchar_unlocked(); break; } for(;ip>='0'&&ip<='9';ip=getchar_unlocked()) ret=ret*10+ip-'0'; return flag*ret; } int main(int argc, char** argv){ register int i, j, k, l,plus,minus; for(i=1;i<=181; i++){ minus = MAXN-i*i; for(j = 0; j<=i && minus >= j*j; j++) for(k = 0; k<=j && (minus-j*j)>= k*k; k++) { plus = j*j + k*k; for (l = 0; l <= k && (minus - plus) >= l * l; l++) DP[i * i + plus + l * l]++; } } k = scan_d(); for(i = 1; i <= k; ++i){ j = scan_d(); printf("#%d %d\n",i,DP[j]); } return 0; }
|