Problem:


Score : 300 points

Problem Statement

Let f(n) be the number of triples of integers (x,y,z) that satisfy both of the following conditions:

1 \leq x,y,z

x^2 + y^2 + z^2 + xy + yz + zx = n

Given an integer N, find each of f(1),f(2),f(3),\ldots,f(N).

Constraints

All values in input are integers.

1 \leq N \leq 10^4

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the value f(i).

Sample Input 1

20

Sample Output 1

0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

For n=6, only (1,1,1) satisfies both of the conditions. Thus, f(6) = 1.

For n=11, three triples, (1,1,2), (1,2,1), and (2,1,1), satisfy both of the conditions. Thus, f(6) = 3.

For n=17, three triples, (1,2,2), (2,1,2), and (2,2,1), satisfy both of the conditions. Thus, f(17) = 3.

For n=18, three triples, (1,1,3), (1,3,1), and (3,1,1), satisfy both of the conditions. Thus, f(18) = 3.



Sample input:
20


Sample output:
0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def f(x, y, z):
    return x**2 + y**2 + z**2 + x * y + y * z + z * x


def count(x, y, z):
    if x == y == z:
        return 1
    elif x == y or y == z:
        return 3
    else:
        return 6


def solve(n):
    x = 1
    ans = 0
    Z_MAX = int(n**0.5) + 1
    while f(x, x, x) <= n:
        y = x
        while f(x, y, y) <= n:
            z_min = y
            z_max = Z_MAX
            while z_max - z_min > 1:
                # print(z_max, z_min)
                t = (z_max + z_min) // 2
                if f(x, y, t) < n:
                    z_min = t + 1
                elif f(x, y, t) > n:
                    z_max = t
                else:
                    z_min = t
            if f(x, y, z_min) == n:
                ans += count(x, y, z_min)

            y += 1
        x += 1

    return ans


def main():
    N = int(input())
    for i in range(1, N + 1):
        print(solve(i))

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
cnt=0
ans=[]
for i in range(2,int((2*n)**0.5)+1):
    for j in range(2,int((2*n)**0.5)+1):
        for k in range(2,int((2*n)**0.5)+1):
            if (i*i + j*j + k*k)%2==0 and (i*i + j*j + k*k)<=2*n and (i+j-k>1) and (i+k-j>1) and (k+j-i>1):
                ans.append((i*i + j*j + k*k)//2)
ans.sort()
A=Counter(ans)
for i in range(1,n+1):
    print(A[i])

Submission status: Accepted

Solution code:
import math
n = int(input())
f_dict = dict()
n_sqrt = int(math.sqrt(n))
for x in range(1,n_sqrt+1):
    for y in range(1,n_sqrt+1):
        for z in range(1,n_sqrt+1):
            f_dict[x*(x+y+z)+y*(y+z)+z*z] = f_dict.get(x*(x+y+z)+y*(y+z)+z*z,0) + 1

for i in range(1,n+1):
    print(f_dict.get(i,0))

Submission status: Accepted

Solution code:
from sys import stdin
import math
n = int(stdin.readline().rstrip())
m = int(n**0.5) +2

data =[0] *100000
tmp = 0
# # x + y + z =3以上
for x in range (1, m):
    for y in range(1, m):
        for z in range(1, m):
            tmp = x*x + y*y + z*z + x*y + y*z + z*x
            if tmp <= n :
                data[tmp] += 1

#配列の0番目除く
for i in range(1,n+1):
    print(data[i])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

N = int(input())

ans = [0] * (N+5)
queue = deque()
queue.append((1,1,1))
total = 0
seen = set()

seen.add((1,1,1))
while queue:
    x,y,z = queue.popleft()
    total = x ** 2 + y ** 2 + z ** 2 + x*y + y*z + z*x

    if total - 1 <= N:
        ans[total-1] += 1
    if total > 2*N+1:
        break

    if (x+1,y,z) not in seen:   
        queue.append((x+1,y,z))
        seen.add((x+1,y,z))
    if (x,y+1,z) not in seen:    
        queue.append((x,y+1,z))
        seen.add((x,y+1,z))
    if (x,y,z+1) not in seen:
        queue.append((x,y,z+1))
        seen.add((x,y,z+1))
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import numpy as np
 
N = int(input())
 
output = np.zeros(N)
 
for x in range(1,int(np.sqrt(N))+1):
    for y in range(1,x+1):
        if x**2 + y**2 + x*y > N:
            break
        for z in range(1,y+1):
            index = x**2 + y**2 + z**2 + x*y + y*z + z*x
            
            if index > N:
                break
            
            dup = len(set([x,y,z]))
            
            if dup == 3:
                output[index-1] += 6
            elif dup == 2:
                output[index-1] += 3
            elif dup == 1:
                output[index-1] += 1
                
for i in range(N):
    print(int(output[i]))

Submission status: Accepted

Solution code:
# n = x^2 + y^2 + z^2 + xy + yz +zx = ((x+y)^2 + (y+z)^2 + (x+z)^2)/2
# 1 <= x, y, z
# n >= 6

import math

N = int(input())
ans = [0] * N

#lim = int(math.sqrt(N/2))
lim = int(math.sqrt(N))
for x in range(1, lim):
    for y in range(1, lim):
        for z in range(1, lim):
            #calc = ((x+y)**2 + (y+z)**2 + (x+z)**2) /2
            calc = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if calc <= N:
                ans[calc -1] += 1

#print(ans)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import math
n = int(input())
nlist = [0]*n
for x in range(1,math.ceil(math.sqrt(n-1)-1)):
    for y in range(1,math.ceil(math.sqrt(n-1)-1)):
        for z in range(1,math.ceil(math.sqrt(n-1)-1)):
            temp = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if temp > n:
                break
            else:
                nlist[temp-1] +=1

for num in nlist:
    print(num)

Submission status: Accepted

Solution code:
import math
from itertools import combinations_with_replacement

def calc(t):
    return t[0]*t[0] + t[1]*t[1] + t[2]*t[2] + t[0]*t[1] + t[1]*t[2] + t[2]*t[0]


n = int(input())
ans = [0]*n
n_root = math.floor(math.sqrt(n))+1

for pattern in combinations_with_replacement(range(1, n_root + 1), 3):
    pattern = list(pattern)
    buf = calc(pattern)
    #print(pattern)
    if buf <= n:
        if pattern[0] == pattern[1] == pattern[2]:
            ans[buf-1] += 1
        elif pattern[0] == pattern[1] or pattern[1] == pattern[2] or pattern[0] == pattern[2]:
            ans[buf-1] += 3
        else:
            ans[buf-1] += 6

[print(a) for a in ans]
#print(ans)

Submission status: Accepted

Solution code:
# 
import sys

from sys import stdin
input = lambda: stdin.readline().rstrip()

N = int(input())

l = [0] * N
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            v = x**2+y**2+z**2+x*y+y*z+z*x
            if v <= N:
                l[v-1] = l[v-1] + 1

for i in l:
    print(i)