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:
N = int(input())
n = 10**4
tmp = [0]*((10**4)+1)
for x in range(1,int(-(-n**0.5//1))+1):
    for y in range(1,x+1):
        for z in range(1, y+1):
            if x*x + y*y + z*z + x*y + y*z + z*x <= 10**4:
                if x == y and y == z and z == x:
                    tmp[x*x + y*y + z*z + x*y + y*z + z*x] +=1
                elif x == y or y == z or z == x:
                    tmp[x*x + y*y + z*z + x*y + y*z + z*x]  += 3
                else:
                    tmp[x*x + y*y + z*z + x*y + y*z + z*x]  += 6
for i in range(1, N+1):
    print(tmp[i])

Submission status: Accepted

Solution code:
N = int(input())

list=[0]*N
for x in range(1,N+1):
    if x * x+2*x+3 > N:
        break
    for y in range(1,N+1):
        if x * x + y * y + x * y+x+y+1 > N:
            break
        for z in range(1, N + 1):
            val=x * x + y * y + z * z + x * y + y * z + z * x
            if val > N:
                break
            list[val - 1] += 1
for i in range(N):
    print("{}".format(list[i]))

Submission status: Accepted

Solution code:
import math

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

for x in range(1,max):
  for y in range(1,max):
    for z in range(1,max):
      ns = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if ns <= n:
        ans[ns-1] += 1
for a in range(n):
  print(ans[a])

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools
import math

N = int(input())
saidai = int(math.sqrt(N)) + 1

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

def f(n):
    result = [0] * (n+1)
    for idx, (x, y, z) in enumerate(itertools.product(range(1, saidai + 1), repeat=3)):
        tmp = g(int(x), int(y), int(z))
        if tmp <= N:
            result[tmp] += 1
    return result

res = f(N)
for i in range(1, N+1):
    print(res[i])

Submission status: Accepted

Solution code:
import math

N = int(input())
for i in range(1,N+1):
    count = 0
    for x in range(1,int(math.sqrt(i/6))+2):
        for y in range(x,int(math.sqrt(i/3))+2):
            for z in range(y,int(math.sqrt(i))+1):
                if x**2+y**2+z**2+x*y+y*z+z*x != i:
                    continue
                if x == y and x == z:
                    count += 1
                elif x == y or x == z or y == z:
                    count += 3
                else:
                    count += 6
    print(count)

Submission status: Accepted

Solution code:
import math

n = int(input())

a = [0]*n

for x in range(1, int(math.sqrt(n))+1):
    for y in range(1, x+1):
        for z in range(1, y+1):
            t = x**2+y**2+z**2+x*y+y*z+z*x-1
            if t >= n:
                break
            if x == y == z:
                a[t] += 1
            elif (x!=y)and(y!=z)and(x!=z):
                a[t] += 6
            else:
                a[t] += 3

for i in range(n):
    print(a[i])

Submission status: Accepted

Solution code:
def func(a, b, c):
    return a**2 + b**2 + c**2 + a*b + b*c + c*a

n = int(input())
ans = [0]*(n+1)
x, y, z = (1, 1, 1)
flag = 0
while flag == 0:
    if func(x, 1, 1) <= n:
        for y in range(1, x+1):
            for z in range(1, y+1):
                num = func(x, y, z)
                if num <= n and x == y == z:
                    ans[num] += 1
                elif num <= n and (x == y or y == z or z == x):
                    ans[num] += 3
                elif num <= n:
                    ans[num] += 6
    else:
        flag = 1
    x += 1

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import math
n = int(input())
# ans = [0 for _ in range(n)]
ans = [0] * n

for x in range(1, int(math.sqrt(n+1))):
    x2 = x*x
    for y in range(1, int(math.sqrt(n+1))):
        y2 = y*y
        xy = x * y
        tmp = x2 + y2 + xy
        if tmp >= n:
            break
        for z in range(1, int(math.sqrt(n+1))):
            tmp2 = tmp + z*z + y*z + z*x
            if tmp2 > n:
                break
            try:
                ans[tmp2 - 1] += 1
                # print(x, y, z)
            except:
                pass
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    #a>=b>=c (a,b,c)->(x,y,z) no junnretu kakeru
    ans=[0]*N
    for a in range(1,101):
        for b in range(1,a+1):
            for c in range(1,b+1):
                temp=((a+b)**2+(c+b)**2+(a+c)**2)//2
                if temp>N:break
                #print(a,b,c,temp)

                if a==b:
                    if b==c:
                        cnt=1
                    else:
                        cnt=3
                elif b==c:cnt=3
                else:cnt=6
                ans[temp-1]+=cnt
    print(*ans,sep="\n")
#%%submit!
resolve()

Submission status: Accepted

Solution code:
n = int(input())

n_list = [0]*50000
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            if x+y+z >= 150:
                break
            index = x*x + y*y + z*z + x*y + y*z + z*x
            n_list[index] = n_list[index]+1

for i in range(1,n+1):
    print(n_list[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[23]:


import math
import itertools


# In[27]:


N = int(input())


# In[28]:


for i in range(1,N+1):
#     print("f(%s)"%i)
    ans = 0
    for x in range(1,int(math.sqrt(i))+1):
        if i - x**2 - x > 0:
            for y in range(x,int(math.sqrt(i-x**2-x))+1):
                if i - x**2 - x - y**2 - y - x*y > 0:
                    for z in range(y,int(math.sqrt(i-x**2-x-y**2-y-x*y)+1)):
                        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                            if x==y and y==z:
                                ans += 1
                            elif x==y:
                                ans += 3
                            elif y==z:
                                ans += 3
                            else:
                                ans += 6
    print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
import itertools
N = int(input())

lis = [0] * (10000 + 1)
for x, y, z in itertools.combinations_with_replacement(range(1, 99), 3):
  calc = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + x * z
  if calc > 10000:
    continue
    
  if x == y and y == z:
    lis[calc] += 1
  elif x == y or y == z or x == z:
    lis[calc] += 3
  else:
    lis[calc] += 6
    
for x in lis[1:N+1]:
  print(x)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

l = [0] * 10 ** 5
for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            sum = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            l[sum-1] += 1

for p in l[:n]:
    print(p)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())

d = defaultdict(int)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp = x**2 + y**2 + z**2 + x * y + y * z + z * x
            d[tmp] += 1

for i in range(1, n + 1):
    print(d[i])

Submission status: Accepted

Solution code:
n = int(input())
cnt = 0
dp = [0] * (10**4 + 1)
for i in range(1,10**2 + 1):
    for j in range(1,10**2 + 1):
        for k in range(1,10**2 + 1):
            a = i**2 + j ** 2 + k**2 +i*j + j*k + k*i
            if a <= 10 ** 4:
                dp[a] += 1


for i in range(1,n+1):
    print(dp[i])

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
for i in range(1,n+1):
    ans = 0
    maxn = int(math.sqrt((i//6)))
    for x in range(1,maxn+1):
        ret = i - x*x
        maxy = (-x+int(math.sqrt(x*x+3*ret)))//3
        for y in range(1,maxy+1):
            ret2 = ret-y*y-y*x
            r = (x+y)**2 + 4*ret2
            if r == int(math.sqrt(r))**2:
                if (math.sqrt(r)-(x+y))%2 == 0 and ret2 > 0:
                    z = (math.sqrt(r)-(x+y))//2
                    if x <= y <= z:
                        if x != y and y != z:
                            ans+=6
                        elif not (x == y and y == z):
                            ans+=3
                        else:
                            ans+=1
    print(ans)

Submission status: Accepted

Solution code:
import itertools as it


def main():
    N = int(input())
    ans = {n:[] for n in range(1,N+1)}


    for x in range(1, 110):
        if x**2 + 2*x> N:
            break
        
        for y in range(1, x+1):
            if x**2 + y**2 > N:
                break
            for z in range(1, y+1):
                t = x*x + y*y + z*z + x*y + y*z + z*x
                if t > N:
                    break
                ans[t].append((x, y, z))
        
    for v in ans.values():
        num = 0
        for x, y, z in v:
            if x == y and y == z:
                num += 1
            elif x == y or y == z or z == x:
                num += 3
            else:
                num += 6
        
        print(num)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
fn = [0]*N

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

print(*fn,sep="\n")

Submission status: Accepted

Solution code:
N = int(input())
ans = [0] * N
sqrt_N = (int(N**0.5 + 1))

for x in range(1,sqrt_N):
    for y in range(1,sqrt_N):
        for z in range(1,sqrt_N): 
            xyz = (x**2)+(y**2)+(z**2)+(x*y)+(y*z)+(z*x)
            if xyz <= N:
                ans[xyz - 1] = ans[xyz - 1] + 1

[print(i) for i in ans]

Submission status: Accepted

Solution code:
ans = [0] * 10**6

for x in range(1, 99):
    for y in range(1, 99):
        for z in range(1, 99):
            ans[(x + y + z)**2 - x * y - x * z - y * z] += 1

n = int(input())

for i in range(1, n + 1):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
count = [0] * (N + 1)
for x in range(1, 100):
    if 2 * ((x + 1) ** 2) + 4 > 2 * N:
        break
    for y in range(1, 100):
        if ((x + y) ** 2 + (y + 1) ** 2 + (1 + x) ** 2) > 2 * N:
            break
        for z in range(1, 100):
            # print(x, y, z)
            score = ((x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2) // 2
            if score > N:
                break
            else:
                count[score] += 1
for i in range(1, N + 1):
    print(count[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
def fn(x,y,z):
    return x**2 + y**2 + z**2 + x*y + y*z + x*z
def cnt(x,y,z):
    n = len(set([x,y,z]))
    if n == 3:
        return 6
    elif n == 2:
        return 3
    else:
        return 1
    
d = defaultdict(int)

for x in range(1,101):
    ix = fn(x,1,1)
    if ix > n:
        break
    for y in range(x,101):
        iy = fn(x,y,1)
        if iy > n:
            break
        for z in range(y,101):
            i = fn(x,y,z)
            if i <= n:
                d[fn(x,y,z)] += cnt(x,y,z)
            else:
                break
                
for i in range(1,n+1):
    print(d[i])

Submission status: Accepted

Solution code:
N = int(input())

list = [0]*(10**4)

for x in range(1,100+1):
  for y in range(1,100+1):
    for z in range(1,100+1):
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if(n <= 10**4):
        list[n-1] += 1
      
for i in range(N):
  print(list[i])

Submission status: Accepted

Solution code:
import math
N = int(input())
counts = [0] * N
for x in range(1, N, 1):
    if x**2>N:
        break
    for y in range(1, N, 1):
        if y**2 > N:
            break
        for z in range(1, N, 1):
            if z**2 > N:
                break
            i = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
            # print(x,y,z,i)
            if i <= N:
                counts[i - 1] += 1
for k in counts:
    print(k)