Problem:


Problem B: Lagrange's Four-Square Theorem

The fact that any positive integer has a representation as the sum of at most four positive
squares (i.e. squares of positive integers) is known as Lagrange’s Four-Square Theorem. The
first published proof of the theorem was given by Joseph-Louis Lagrange in 1770. Your mission
however is not to explain the original proof nor to discover a new proof but to show that the
theorem holds for some specific numbers by counting how many such possible representations
there are.

For a given positive integer n, you should report the number of all representations of n as the
sum of at most four positive squares. The order of addition does not matter, e.g. you should
consider 42 + 32 and 32 + 42 are the same representation.

For example, let’s check the case of 25. This integer has just three representations 12 +22 +22 +42 ,
32 + 42 , and 52 . Thus you should report 3 in this case. Be careful not to count 42 + 32 and
32 + 42 separately.

Input

The input is composed of at most 255 lines, each containing a single positive integer less than
215 , followed by a line containing a single zero. The last line is not a part of the input data.

Output

The output should be composed of lines, each containing a single integer. No other characters
should appear in the output.

The output integer corresponding to the input integer n is the number of all representations
of n as the sum of at most four positive squares.

Sample Input

1
25
2003
211
20007
0

Output for the Sample Input

1
3
48
7
738



Sample input:
1
25
2003
211
20007
0


Sample output:
1
3
48
7
738

Submission status: Wrong Answer

Solution code:
a=[[0]*5 for _ in [0]*(1<<15)]
for i in range(int((1<<15)**.5)):
    a[i*i][1]+=1
    for j in range(i*i+1,min(4*i*i+1,1<<15)):
        for k in range(2,5):
            a[j][k]+=a[j-i*i][k-1]
while 1:
    n=int(input())
    if n==0:break
    print(sum(a[n]))

Submission status: Wrong Answer

Solution code:
R = 2**15+1
dp = [[0]*R for i in range(4)]
for i in range(1,182):
	dp[0][i**2] += 1
for k in range(1,4):
	for i in range(1,182):
		for j in range(R-i**2):
			dp[k][j+i**2] += dp[k-1][j]

while 1:
	n = input()
	if n == 0: break
	print sum(dp[i][n] for i in range(4))

Submission status: Wrong Answer

Solution code:
R = 2**15+1
dp = [[0]*R for i in range(4)]
for i in range(1,182):
	dp[0][i**2] += 1
for k in range(1,4):
	for i in range(1,182):
		for j in range(i**2,R-i**2):
			dp[k][j+i**2] += dp[k-1][j]

while 1:
	n = input()
	if n == 0: break
	print sum(dp[i][n] for i in range(4))

Submission status: Wrong Answer

Solution code:
R = 2**15+1
dp = [[0]*R for i in range(4)]
for i in range(1,182):
	dp[0][i**2] += 1
for k in range(1,4):
	for i in range(1,182):
		for j in range(i*i,R):
			dp[k][j] += dp[k-1][j-i*i]

while 1:
	n = input()
	if n == 0: break
	print sum(dp[i][n] for i in range(4))

Submission status: Wrong Answer

Solution code:
R = 2**15+1
dp = [[0]*R for i in range(5)]
dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = 1
for i in range(1,182):
	for k in range(1,5):
		for j in range(i*i,R-i*i):
			dp[k][j+i*i] += dp[k-1][j]

while 1:
	n = input()
	if n == 0: break
	print dp[4][n]

Submission status: Accepted

Solution code:
from math import sqrt
MAX = 2**15-1
ub = int(sqrt(MAX))
square_sum = [[0 for i in range(MAX)] for j in range(4)]
for k in range(1,ub+1):
	square_k = k**2
	square_sum[0][square_k-1] = 1 
	for j in range(3):
		for i in range(1,MAX - square_k + 1):
			if square_sum[j][i-1] >= 1:
				square_sum[j+1][i-1+square_k] += square_sum[j][i-1]
while 1:
	n = int(raw_input())
	if n == 0:
		break
	print sum(square_sum[i][n-1] for i in range(4))

Submission status: Accepted

Solution code:
a=[[0]*5 for _ in [0]*(1<<15)]
for i in range(int((1<<15)**.5)+1):
    a[i*i][1]+=1
    for j in range(i*i+1,min(4*i*i+1,1<<15)):
        for k in range(2,5):
            a[j][k]+=a[j-i*i][k-1]
while 1:
    n=int(input())
    if n==0:break
    print(sum(a[n]))

Submission status: Accepted

Solution code:
MAXN = 2**15
MAXRT = int(MAXN**0.5)
MAXTERM = 4

dp = [[0 for n in range(MAXN+1)] for t in range(MAXTERM+1)]
dp[0][0] = 1
for r in range(MAXRT,0,-1):
    for t in range(MAXTERM):
        for n in range(MAXN+1 - r*r):
            if dp[t][n] == 0: continue
            dp[t+1][n + r*r] += dp[t][n]

while True:
    N = int(input())
    if N == 0: break
    print(sum(map(lambda x:x[N],dp)))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    m = 2**15
    a = [[0]*(m+1) for _ in range(5)]
    a[0][0] = 1
    for i in range(1,m):
        ii = i**2
        if ii > m:
            break
        for k in range(4):
            for j in range(ii,m+1):
                a[k+1][j] += a[k][j-ii]

    def f(n):
        r = 0
        for i in range(5):
            r += a[i][n]
        return r

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
R = 2**15+1
dp = [[0]*R for i in range(5)]
dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = 1
for i in range(1,182):
	for k in range(1,5):
		for j in range(i*i,R):
			dp[k][j] += dp[k-1][j-i*i]

while 1:
	n = input()
	if n == 0: break
	print dp[4][n]

Submission status: Accepted

Solution code:
R = 2**15+1
r = 182
s = [i*i for i in range(r)]
L = [0]*R
for i in range(r):
	for j in range(i,r):
		for k in range(j,r):
			for l in range(k,r):
				if s[i]+s[j]+s[k]+s[l] < R:
					L[s[i]+s[j]+s[k]+s[l]] += 1

while 1:
	n = input()
	if n == 0: break
	print L[n]

Submission status: Accepted

Solution code:
def initSquaresArray():
    arr = []
    n = 1
    while True:
        if n * n >= 32768:
            break
        arr.append(n * n)
        n += 1
    return arr

def get2Squares(num):
    global squares
    global memo2

    if num in memo2:
        return memo2[num]

    squareSums = set()
    for square in squares:
        if square >= num:
            break
        if num - square in squares:
            squareSums.add( (min(square, num - square), max(square, num - square)) )
    
    memo2[num] = squareSums
    return memo2[num]

def get3Squares(num):
    global squares
    global memo3

    if num in memo3:
        return memo3[num]

    squareSums = set()
    for square in squares:
        if square >= num:
            break
        other = get2Squares(num - square)
        for o in other:
            a = square
            b = o[0]
            c = o[1]
            tpl = tuple(sorted([ a, b, c ]))
            squareSums.add(tpl)

    memo3[num] = squareSums
    return memo3[num]

def get4Squares(num):
    global squares
    global memo4

    if num in memo4:
        return memo4[num]

    squareSums = set()
    for square in squares:
        if square >= num:
            break
        other = get3Squares(num - square)
        for o in other:
            a = square
            b = o[0]
            c = o[1]
            d = o[2]
            tpl = tuple(sorted([ a, b, c, d ]))
            squareSums.add(tpl)

    memo4[num] = squareSums
    return memo4[num]

if __name__ == '__main__':
    memo2 = {}
    memo3 = {}
    memo4 = {}
    squares = initSquaresArray()
    
    while True:
        num = int(input())
        if num == 0:
            break

        s2 = get2Squares(num)
        s3 = get3Squares(num)
        s4 = get4Squares(num)

        count = 1 if num in squares else 0
        count += len(s2)
        count += len(s3)
        count += len(s4)

        print(count)

Submission status: Runtime Error

Solution code:
from math import sqrt
while 1:
	n = int(raw_input())
	if n == 0:
		break
	ub = int(sqrt(n))
	square_sum = [[0 for i in range(n+1)] for j in range(4)]
	for k in range(1,ub+1):
		square_k = k**2
		square_sum[0][square_k] = 1
		for j in range(3):
			for i in range(1, n+1 - square_k):
				if square_sum[j][i] >= 1:
					square_sum[j+1][i+square_k] += square_sum[j][i]
	print sum([square_sum[j][n] for j in range(4)])

Submission status: Runtime Error

Solution code:
from math import sqrt
while 1:
	n = int(raw_input())
	if n == 0:
		break
	ub = int(sqrt(n))
	square = [i**2 for i in range(1,ub+1)]
	square_sum =[[0 for i in range(n)] for j in range(2)]
	count = 0
	for k in range(1,ub+1):
		for i in range(1,k+1):
			if square[k-1] + square[i-1] <= n: 
				square_sum[0][square[k-1] + square[i-1]-1] += 1
		for i in range(1, n + 1 - square[k-1]):
			if square_sum[0][i-1] >= 1:
				square_sum[1][i-1+square[k-1]] += square_sum[0][i-1]
		count += square_sum[1][n-1-square[k-1]]
	print (1 if n == ub**2 else 0) + square_sum[0][n-1] + square_sum[1][n-1] + count

Submission status: Runtime Error

Solution code:
import math
LIM = 182

def solve(n):
    ans = 0
    for a in range(1,LIM):
        tmp = a*a
        if tmp == n:
            ans += 1
        if tmp >= n:
            break
        for b in range(a,LIM):
            tmp2 = tmp + b*b
            if tmp2 == n:
                ans += 1
            if tmp2 >= n:
                break
            for c in range(b,LIM):
                tmp3 = tmp2 + c*c
                if tmp3 == n:
                    ans += 1
                if tmp3 >= n:
                    break
                d = int(math.sqrt(n - tmp3))
                if tmp3 + d*d == n and c <= d:
                    ans += 1
    return ans

while True:
    N = int(input())
    if N == 0: break
    print(solve(N))

Submission status: Runtime Error

Solution code:
import math
LIM = 182

def is_square(n):
    a = int(math.sqrt(n))
    return a*a == n

def solve(n):
    ans = 0
    if is_square(n):
        ans += 1
    for a in range(1,LIM):
        if a*a*2 > n:
            break
        if is_square(n - a*a):
            ans += 1
        for b in range(a,LIM):
            if b*b*2 > (n - a*a):
                break
            if is_square(n - a*a - b*b):
                ans += 1
            for c in range(b,LIM):
                if c*c*2 > (n - a*a - b*b):
                    break
                tmp = n - a*a - b*b - c*c
                if is_square(tmp) and c*c <= tmp:
                    ans += 1
    return ans

while True:
    N = int(input())
    if N == 0: break
    print(solve(N))

Submission status: Runtime Error

Solution code:
import sys
import bisect
import itertools as it

square = []

i = 0
while i*i <= 2**15:
    square.append(i*i)
    i += 1

L = len(square)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    count = 0
    for i in xrange(L):
        for j in xrange(i, L):
            for k in xrange(j, L):
                v = n - square[i] - square[j] - square[k]
                idx = bisect.bisect_left(square, v)
                if idx >= k and square[idx] == v:
                    count += 1
    print count

Submission status: Runtime Error

Solution code:
import sys
import bisect
import itertools as it

square = []

i = 0
while i*i <= 2**15:
    square.append(i*i)
    i += 1

L = len(square)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    count = 0
    for i in xrange(L):
        for j in xrange(i, L):
            for k in xrange(j, L):
                v = n - square[i] - square[j] - square[k]
                idx = bisect.bisect_left(square, v)
                if L > idx >= k and square[idx] == v:
                    count += 1
    print count

Submission status: Runtime Error

Solution code:
import sys
import bisect
square = []

i = 0
while i*i <= 2**15:
    square.append(i*i)
    i += 1

L = len(square)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    count = 0
    for i in xrange(L):
        for j in xrange(i, L):
            for k in xrange(j, L):
                v = n - square[i] - square[j] - square[k]
                idx = bisect.bisect_left(square, v)
                if L > idx >= k and square[idx] == v:
                    count += 1
    print count

Submission status: Runtime Error

Solution code:
import math
while True:
    n=input()
    if n==0:break
    S=set()
    P=set([i*i for i in range(182)])
    for	i in range(182):
	if i>n:break
	for j in range(182):
            if i+j>n:break
            for k in range(182):
		if i+j+k>n:break
                if n-32761<=i*i+j*j+k*k<=n and ((n-(i*i+j*j+k*k)) in P):
		    l=[i,j,k,int(round(math.sqrt(n-(i*i+j*j+k*k))))]
                    l.sort()
                    S.add(tuple(l))
    print len(S)

Submission status: Runtime Error

Solution code:
while True:
    n=input()
    if n==0:break
    cnt=0
    for i in range(182):
	if i*i>n:break
	for j in range(i,182):
            if i*i+j*j>n:break
            for k in range(j,182):
		if i*i+j*j+k*k>n:break
		for l in range(k,182):
                    if i*i+j*j+k*k+l*l>n:break
                    if i*i+j*j+k*k+l*l==n: cnt+=1
    print cnt