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())

def f(x, y, z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x
lst = [0 for i in range(n)]
for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            num = f(i, j, k)
            if num <= n:
                lst[num-1] += 1

for i in lst:
    print(i)

Submission status: Accepted

Solution code:
from math import sqrt
def f(x,y,z):
  return x**2+y**2+z**2+x*y+y*z+z*x

N=int(input())
n = int(sqrt(N))+5
count = [0 for i in range(N+1)]
for i in range(1,n):
  for j in range(1,n):
    for k in range(1,n):
      out = f(i,j,k)
      if out <= N:count[out] += 1
for i in range(1,N+1):
  print(count[i])

Submission status: Accepted

Solution code:
n= int(input())
ans=[0]*(n+1)
v=10**2
for x in range(1,v+1):
    for y in range(1,v+1):
        for z in range(1,v+1):
            cnt=pow(x,2)+pow(y,2)+pow(z,2)+x*y+y*z+z*x
            if cnt<=n:
                ans[cnt]+=1

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

Submission status: Accepted

Solution code:
import math

N = int(input())

n = int(math.sqrt(N)) + 1

res = [set() for _ in range(N)]

for x in range(1, n+1):
    for y in range(1, n+1):
        for z in range(1, n+1):
            enu = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if enu <= N:
                res[enu-1].add((x, y, z))

for i in range(N):
    print(len(res[i]))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N = int(input())
dic=dd(int)
for x in range(1,N+1):
    t1 = N-x**2
    if t1 <= 1:
        continue
    for y in range(1,t1+1):
        t2 = N-x**2-y**2
        if t2 <= 0:
            continue
        for z in range(1,t2+1):
            tmp = x**2+y**2+z**2+x*y+y*z+z*x
            if tmp > N:
                break
            else:
                dic[tmp] += 1

for i in range(N):
    print(dic[i+1])

Submission status: Accepted

Solution code:
N = int(input())

ans = [0]*(N+1)

for x in range(1,100,1):
    for y in range(1,100,1):
        for z in range(1,100,1):
            tmp = x*x+y*y+z*z+x*y+y*z+z*x
            if 0 < tmp and tmp <=N:
                ans[tmp]+=1


for i in ans[1:len(ans)]:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
di = {}
for i in range(1,1000000):
    di[i] = 0
for i in range(1, 150):
    for j in range(1, 150):
        for k in range(1, 150):
            di[i**2+j**2+k**2+i*j+j*k+k*i] += 1
for i in range(1, n+1):
    print(di[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    ans = [0]*(N+1)
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                n = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if n<=N:
                    ans[n] += 1
    print(*ans[1:])




main()

Submission status: Accepted

Solution code:
import itertools
def main():
    N = int(input())
    xyz = itertools.product(range(1, 101), repeat=3)

    ans = [0] * (N + 1)
    for (x, y, z) in xyz:
        # print(x, y, z)
        f = x*x + y*y + z*z + x*y + y*z + z*x
        if f <= N:
            ans[f] += 1

    ans = ans[1:]
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

max_n=10**4+5
ans=[0]*(max_n+1)
for x in range(1,105):
    for y in range(1,105):
        for z in range(1,105):
            total=x**2+y**2+z**2+x*y+y*z+z*x
            if total<=max_n:
                ans[total]+=1

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

Submission status: Accepted

Solution code:
N = int(input())

f = [0] * (10 ** 4 + 1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if n <= 10 ** 4:
                f[n] += 1
print(*f[1 : N + 1], sep="\n")

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n = ni()
ans = [0]*n
def f(x,y,z):
    return x**2 + y**2+ z**2 +x*y+y*z+z*x
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            s = f(x,y,z)
            if  s<=n:
                ans[s-1] +=1
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
R = [0] * 10001
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            res = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if res<=10000:
                R[res] += 1
for n in range(1,N+1):
    print(R[n])

Submission status: Accepted

Solution code:
N = int(input())
ans_list =[0] * 1000000
for i in range(100):
  a = i+1
  for j in range(100):
    b = j+1
    for l in range(100):
      c = l+1
      ans_list[(a**2+b**2+c**2+a*b+a*c+b*c)-1] += 1
for i in range(N):
  print(ans_list[i])

Submission status: Accepted

Solution code:
from math import gcd

from math import factorial as f

from math import ceil, floor, sqrt
import math

import bisect
import re
import heapq

from copy import deepcopy
import itertools
from itertools import permutations

from sys import exit

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

yes = "Yes"
no = "No"


def main():
    n = ii()
    ans = [0 for i in range(n + 5)]
    for i in range(1,200):
        for j in range(1,200):
            for k in range(1,200):
                tmp = ((i + j)**2 + (j + k)**2 + (k + i)**2)
                if tmp <= 2 * n + 5 and tmp % 2 == 0:
                    ans[tmp // 2] += 1
    for i in range(1, n + 1):
        print(ans[i])


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections

def solve(N: int):
    count = collections.defaultdict(int)
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                value = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
                if value > N:
                    break
                count[value] += 1

    for i in range(1, N+1):
        print(count[i])
    
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def main():
    N = int(input())
    l = [0] * (N+1)
    x = int(math.sqrt(N)) + 2
    for i in range(1, x):
        for j in range(1, x):
            for k in range(1, x):
                t = i**2 + j**2 + k**2 + i*j + j*k + k*i
                if t <= N:
                    l[t] += 1
    for i in range(1, N+1):
        print(l[i])
main()

Submission status: Accepted

Solution code:
N = int(input())
l = [0] * (10**5)
for x in range(1,101):
  x_2 = x**2
  for y in range(1,101):
    y_2 = y**2
    xy = x*y
    for z in range(1,101):
      n = x_2 + y_2 + z**2 + xy + x*z + y*z
      l[n] += 1
      
for i in range(1,N+1):
  print(l[i])

Submission status: Accepted

Solution code:
N=int(input())
l=[0]*(10**4+1)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            num=pow(i,2)+pow(j,2)+pow(k,2)+i*j+j*k+k*i
            if num<=10**4:
                l[num]=l[num]+1
for i in range(1,N+1):
    print(l[i])

Submission status: Accepted

Solution code:
N = int(input())

t = [0] * (10 ** 4 + 1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x * x + y * y + z * z + x * y + y * z + z * x
            if n <= 10 ** 4:
                t[n] += 1

print(*[t[i] for i in range(1, N + 1)], sep='\n')

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())

    f = [0] * (N + 1)
    for x in range(1, 10 ** 2 + 1):
        for y in range(1, 10 ** 2 + 1):
            for z in range(1, 10 ** 2 + 1):
                n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
                if n <= N:
                    f[n] += 1

    print("\n".join(map(str, f[1:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

dp = [0 for i in range(20000+1)]

for i in range(1,200+1):
	for j in range(1,200+1):
		for k in range(1,200+1):
			po = (i+j)**2 + (j+k)**2 + (k+i)**2
			if po <= 20000:
				dp[po] += 1

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

Submission status: Accepted

Solution code:
n = int(input())

ans = [0] * (n+1)


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


for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            c = f(x, y, z)
            if c <= n:
                ans[c] += 1

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

Submission status: Accepted

Solution code:
n = int(input())

ans = dict()
for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            now = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            if now not in ans:
                ans[now] = 1
            else:
                ans[now] += 1

for i in range(1, n + 1):
    if i not in ans:
        print(0)
    else:
        print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())

A = [0 for i in range(10**4+1)]

for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      a = x*x + y*y + z*z + x*y + y*z + z*x
      if a <= 10**4:
        A[a] += 1

for i in range(1, N+1):
  print(A[i])

Submission status: Accepted

Solution code:
n = int(input())

count = [0] * 10001

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            temp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if(1 <= temp and temp <= 10000):
                count[temp] += 1

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

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N =iRaw()
    ans = [0]*(N+1)
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                n = x*x+y*y+z*z+x*y+y*z+z*x
                if n<=N:
                    ans[n]+=1
    for i in range(1,N+1):
        print(ans[i])
main()

Submission status: Accepted

Solution code:
# coding: utf-8


def main():
    N = int(input())

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

    for i in range(N):
        print(fs[i])


main()
# print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
res = [0] * (N + 1)
x = 1
while x * x <= N:
  y = 1
  while y * y <= N:
    z = 1
    while z * z <= N:
      if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x in range(1, N + 1):
        res[x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x] += 1
      z += 1
    y += 1
  x += 1 

for r in res[1: ]: print(r)