Problem:


素数の性質

4 で割ると 3 あまる素数 n (11、19、23 など) には、面白い性質があります。1 以上 n 未満の自然数 (1, 2,... , n - 1) を 2 乗したものを n で割ったあまりを計算した結果を並べると、同じ数になるものがあるため、互いに異なった数の個数は、(n - 1)/2 になります。

この様にして得られた数の集合には、特別な性質があります。得られた数の集合から、互いに異なる 2 つ a と b を選んでその差を計算します。差が負になったときは、その差に n を足します。さらに結果が (n - 1)/2 より大きいときは、その差を n から引きます。

例えば、n = 11 のとき 1 と 9 の差は、1 &minus; 9 = &minus;8  → &minus;8 + n = &minus;8 + 11 = 3 になります。9 と 1 の差も 9 &minus;1 = 8 → n &minus; 8 = 11 &minus; 8 = 3 で、同じ値 3 になります。この差は、円周上に 0, 1, ・・・, n - 1 を書いて、二つの数字の間の短い方の円弧を考えるとわかりやすくなります。(下図参照)

  こうして得られた数の「差」は、1, 2, . . ., (n - 1)/2 のいずれかであり、同じ回数出現します。

【例】 n = 11 の時は、以下のようになります。

 1 から n-1 までの数を 2 乗したものを n で割った余りを計算します。

 12  =    1   →   1
 22  =    4   →   4
 32  =    9   →   9
 42  =   16   →   5
 52  =   25   →   3
 62  =   36   →   3
 72  =   49   →   5
 82  =   64   →   9
 92  =   81   →   4
102  =  100   →   1

 a, b の「差」の計算

       

 1 で得られた 1, 3, 4, 5, 9 について異なる数同士の差を計算します。

 計算結果が負の場合、n = 11 を加算します。

 さらに、計算結果が  (n-1)/2 = 5 より大きい場合 n = 11 から減算します。

       

出現回数を求める

計算結果 1, 2, 3, 4, 5 の出現回数をそれぞれ数え上げます。

これらの計算結果から 1, 2, 3, 4, 5 の出現回数が 4 回であることがわかります。この性質は 4 で割ると 3 あまる素数特有の性質であり 4 で割ると 1 あまる素数ではこのようなことはおきません。このことを確認するため、10000 以下の奇数 n を入力とし、例題にあるような計算 (n で割ったあまりの 2 乗の差の頻度を求める)を実行し、その出現回数を出力するプログラムを作成してください。

-->

Input

複数のデータセットが与えられます。各データセットとして１つの整数 n　(n ≤ 10000) が１行に与えられます。入力は 0 を１つ含む行でおわります。

Output

各データセットについて、出現頻度を以下の形式で出力してください。

剰余の平方の差が 1 である(a, b)の出現個数(整数)
剰余の平方の差が 2 である(a, b)の出現個数(整数)
   :
   :
剰余の平方の差が (n-1)/2 である(a, b)の出現個数(整数)

Sample Input

11
15
0

Output for the Sample Input

4
4
4
4
4
2
2
4
2
4
4
2



Sample input:
11
15
0


Sample output:
4
4
4
4
4
2
2
4
2
4
4
2

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n = int(raw_input())
    if n == 0: break
    mod = list(set([i**2%n for i in range(1,n)]))
    hist = [0]*((n-1)/2)
    for i,j in itertools.combinations(mod,2):
        tmp1 = i-j
        if tmp1 < 0: tmp1 += n
        if tmp1 > (n-1)/2: tmp1 = n-tmp1
        tmp2 = j-i
        if tmp2 < 0: tmp2 += n
        if tmp2 > (n-1)/2: tmp2 = n-tmp2
        hist[tmp1-1] += 1
        hist[tmp2-1] += 1
    for i in hist:
        print i

Submission status: Time Limit Exceeded

Solution code:
import itertools
square = [i*i for i in range(1,10001)]
while True:
    n = int(raw_input())
    if n == 0: break
    mod = list(set([i%n for i in square[:n-1]]))
    hist = [0]*((n-1)/2)
    for i,j in itertools.combinations(mod,2):
        tmp1 = i-j
        if tmp1 < 0: tmp1 += n
        if tmp1 > (n-1)/2: tmp1 = n-tmp1
        tmp2 = j-i
        if tmp2 < 0: tmp2 += n
        if tmp2 > (n-1)/2: tmp2 = n-tmp2
        hist[tmp1-1] += 1
        hist[tmp2-1] += 1
    for i in hist:
        print i

Submission status: Time Limit Exceeded

Solution code:
import itertools
square = [i*i for i in range(1,10001)]
while True:
    n = int(raw_input())
    m = (n-1)/2
    if n == 0: break
    mod = set(i%n for i in square[:m])
    hist = [0]*m
    for i,j in itertools.combinations(mod,2):
        tmp1 = i-j
        if tmp1 < 0: tmp1 += n
        if tmp1 > m: tmp1 = n-tmp1
        tmp2 = j-i
        if tmp2 < 0: tmp2 += n
        if tmp2 > m: tmp2 = n-tmp2
        hist[tmp1-1] += 1
        hist[tmp2-1] += 1
    for i in hist:
        print i

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_min = 0
	_max = int((n - 1) / 2)

	print(_min, _max)

	ns = set([ x * x % n for x in range(1, n)])
	count  = {}
	for i in ns:
		for j in ns:
			if i < j:
				m = i - j
				if m < _min: m = n + m
				if m > _max: m = n - m
				count.setdefault(m, 0)
				count[m] += 1
	for i in range(1, int((n - 1) / 2 + 1)):
		print(count[i] * 2)

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_min = 0
	_max = int((n - 1) / 2)

	ns = set([ x * x % n for x in range(1, n)])
	count  = [0 for i in range(0, int((n - 1) / 2) + 1)]
	for i in ns:
		for j in ns:
			if i < j:
				m = i - j
				if m < _min: m = n + m
				if m > _max: m = n - m
				count[m] += 1
	for i in count:
			if i > 0: print(i * 2)

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_max = int((n - 1) / 2)

	ns = set([ x * x % n for x in range(1, n)])
	count  = [0 for i in range(0, int((n - 1) / 2) + 1)]
	for i in ns:
		for j in ns:
			if i > j:
				m = i - j
				if m > _max: m = n - m
				count[m] += 1
	for i in count:
			if i > 0: print(i * 2)

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

pows = [x * x for x in range(1, 10000)]

while True:
	n = int(input())
	if n == 0: break

	_max = int((n - 1) / 2)

	ns = set([x % n for x in pows[0:n]])
	count  = [0 for i in range(0, int((n - 1) / 2) + 1)]
	for i in ns:
		for j in ns:
			if i > j:
				m = i - j
				if m > _max: m = n - m
				count[m] += 1
	for i in count:
			if i > 0: print(i * 2)

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_max = int((n - 1) / 2)
	ns = set([x * x % n for x in range(1, _max + 1)])
	cs = [0 for i in range(0, _max + 1)]

	for i in ns:
		for j in ns:
			if i > j:
				m = i - j
				if m > _max: m = n - m
				cs[m] += 1
	for i in cs:
			if i > 0: print(i * 2)

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_max = int((n - 1) / 2)
	ns = set([x * x % n for x in range(1, _max + 1)])
	cs = {}

	for i in ns:
		for j in ns:
			if i > j:
				m = i - j
				if m > _max: m = n - m
				cs[m] = cs.setdefault(m, 0) + 1
	for i in range(1, _max + 1):
			print(i * 2)

Submission status: Time Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_max = int((n - 1) / 2)
	ns = set([x * x % n for x in range(1, _max + 1)])
	cs = {}

	for i in ns:
		for j in ns:
			if i > j:
				m = i - j
				if m > _max: m = n - m
				cs[m] = cs.setdefault(m, 0) + 2
	s = ''
	for i in range(1, _max + 1):
			s += str(cs[i]) + '\n'
	print(s)

Submission status: Time Limit Exceeded

Solution code:
def f(L):
    while 1 < len(L):
        a = L[0]
        for b in L[1:]:
            check(a-b+n, b-a)
        L = L[1:]
    for k in sorted(res):
        print res[k]
        
def check(*t):
    for v in t:
        if (n-1)/2 < v:
            v = n - v
        if not v in res:
            res[v] = 1
        else:
            res[v] = res[v]+1

while True:
    n = input()
    if n == 0: break
    lis = [(i**2)-n*((i**2)/n) for i in range(1, n)]
    res = {}
    f(sorted(set(lis)))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = input()
    if n==0:
        break
    s = {i*i % n for i in xrange(1, n)}
    c = (n-1)/2
    m = [0] * (c+1)
    for a in s:
        for b in s:
            if a==b:
                continue
            t = a-b
            if t<0: t += n
            if t > c: t = n - t
            m[t] += 1
    print "\n".join(map(str, m[1:]))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = int(raw_input())
    if n==0: break
    s = {i*i % n for i in xrange(1, n)}
    c = (n-1)/2
    m = [0] * (c+1)
    for a in s:
        for b in s:
            if a==b: continue
            t = a-b
            if t<0: t += n
            if t > c: t = n - t
            m[t] += 1
    print "\n".join(map(str, m[1:]))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = int(raw_input())
    if n==0: break
    s = list({i*i % n for i in xrange(1, n)})
    c = (n-1)/2
    m = [0] * (c+1)
    for a in s:
        for b in s:
            if a==b: continue
            t = a-b
            if t<0: t += n
            if t > c: t = n - t
            m[t] += 1
    print "\n".join(map(str, m[1:]))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    D = {x**2 % n for x in xrange(1, n)}
    C = {}
    print D
    for p in D:
        for q in D:
            if p == q:
                continue
            g = (p - q) % n
            if g > (n - 1)/2:
                g = n - g
            C[g] = C.get(g, 0) + 1
    for i in xrange(1, (n-1)/2+1):
        print C.get(i, 0)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    D = {x**2 % n for x in xrange(1, n)}
    C = [0]*((n-1)/2)
    for p in D:
        for q in D:
            if p == q:
                continue
            g = (p - q) % n
            if g > (n - 1)/2:
                g = n - g
            C[g-1] += 1
    print "\n".join(map(str, C))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    D = list({x**2 % n for x in xrange(1, n)})
    C = [0]*((n-1)/2)
    for i in xrange(len(D)):
        p = D[i]
        for j in xrange(i):
            q = D[j]
            g = (p - q) % n
            C[min(g, n-g)-1] += 2
    print "\n".join(map(str, C))

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem 00142: Nature of Prime Numbers
#
import sys, math, os, copy

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


while True:
    n = int(input())
    if n == 0:
        break
    inp = sorted(list(set([i**2 % n for i in range(1, n)])))
    table = [0] * (1 + (n - 1) // 2)
    for i in range(len(inp)):
        for j in range(len(inp)):
            if i == j:
                continue
            c = inp[i] - inp[j]
            if c < 0:
                c += n
            if c > (n - 1) // 2:
                c = n - c
            table[c] += 1
    for i in range(1, (n - 1) // 2 + 1):
        print(table[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

while True:
    num = int(input())

    if num == 0:
        break

    half_num = num // 2

    mod = [item ** 2 % num for item in range(1, num)]
    unique_mod = list(set(mod))

    counter = Counter()

    for item in unique_mod:
        for item2 in unique_mod:
            if item != item2:
                subtract = item - item2

                if subtract < 0:
                    subtract += num
                if half_num < subtract:
                    subtract = num - subtract

                counter[subtract] += 1

    output = ""

    for index in range(1, half_num):
        output += str(counter[index])
        output += "\n"
    output += str(counter[half_num])

    print(output)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

SQUARE_NUM = [item ** 2 for item in range(1, 10001)]

while True:
    num = int(input())

    if num == 0:
        break

    half_num = num // 2

    mod = [item % num for item in SQUARE_NUM[:num - 1]]
    unique_mod = list(set(mod))

    counter = Counter()

    for index, item in enumerate(unique_mod):
        for item2 in unique_mod[index + 1:]:

            subtract = item - item2

            if subtract < 0:
                subtract += num
            if half_num < subtract:
                subtract = num - subtract

            counter[subtract] += 2

    output = [counter[index] for index in range(1, half_num + 1)]
    output = map(lambda item: str(item), output)
    print("\n".join(output))

Submission status: Time Limit Exceeded

Solution code:
import array
import math

SQUARE_NUM = [item ** 2 for item in range(1, 5001)]


def is_prime_number(num):
    if num == 2:
        return True

    if num < 2 or num % 2 == 0:
        return False

    for divisor in range(3, int(math.sqrt(num)) + 1, 2):
        if num % divisor == 0:
            return False

    return True


while True:
    num = int(input())

    if num == 0:
        break

    half_num = num // 2

    if num % 4 == 3 and is_prime_number(num):
        count = str(num // 2 - 1)
        output = [count] * (half_num - 1)
    else:

        mod = [item % num for item in SQUARE_NUM[:half_num]]
        unique_mod = list(set(mod))

        counter = array.array("i", [0] * half_num)

        for index, item in enumerate(unique_mod, 1):
            for item2 in unique_mod[index:]:

                subtract = item - item2

                if subtract < 0:
                    subtract += num

                if half_num < subtract:
                    subtract = num - subtract

                counter[subtract - 1] += 2

        output = [str(item) for item in counter]

    print("\n".join(output))

Submission status: Time Limit Exceeded

Solution code:
from array import array
import itertools

while True:
    num = int(input())

    if num == 0:
        break

    half_num = num // 2

    mod = [pow(item, 2, num) for item in range(1, half_num + 1)]
    unique_mod = array("i", sorted(set(mod), reverse=True))

    counter = array("i", [0] * half_num)

    for item, item2 in itertools.combinations(unique_mod, 2):

        subtract = item - item2

        if half_num < subtract:
            subtract = num - subtract

        counter[subtract - 1] += 2

    output = [str(item) for item in counter]
    print("\n".join(output))

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break

    a = []
    for i in range(1, n):
        k = i**2 % n
        if not k in a:
            a.append(k)

    #print(a)
    b = [0 for i in range((n-1)//2)]
    for i in range(len(a)):
        for j in range(i+1, len(a)):
            k = a[i] - a[j]
            if k < 0:
                k += n
            if k > (n-1)//2:
                k = n - k
            b[k-1] += 1

    for i in range(len(b)):
        print(2*b[i])

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break

    a = []
    for i in range(1, (n+1)//2):
        k = i**2 % n
        if not k in a:
            a.append(k)

    #print(a)
    a.sort()
    b = [0 for i in range((n-1)//2)]
    for i in range(len(a)):
        for j in range(i+1, len(a)):
            k = a[j] - a[i]
            if k > (n-1)//2:
                k = n - k
            b[k-1] += 1

    for i in range(len(b)):
        print(2*b[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def func(n):
  dic = Counter()
  rest = []
  for i in range(1, n):
    rest.append(i ** 2 % n)
  rest = list(set(rest))
  rest.sort()
  lenr = len(rest)
  
  for i in range(lenr):
    for j in range(i + 1, lenr):
      x, y = rest[i], rest[j]
      if y - x > n // 2:
        dic[n - (y - x)] += 2
      else:
        dic[y - x] += 2

  for i in range(1, (n + 1) // 2):
    print(dic[i])
while True:
  n = int(input())
  if n == 0:
    break
  func(n)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def func(n):
  dic = Counter()
  rest = list({i ** 2 % n for i in range(1, n)})
  lenr = len(rest)
  rest.sort()
  half = n // 2
  
  for i in range(lenr):
    resti = rest[i]
    for j in range(i + 1, lenr):
      dff = rest[j] - resti
      if dff > half:
        dic[n - dff] += 2
      else:
        dic[dff] += 2

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

def main():
  while True:
    n = int(input())
    if n == 0:
      break
    func(n)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

while True:
    n=input()
    if n==0:break
    k=(n-1)/2
    L=[]
    ans=[0]*(k+1)
    for i in range(1,n):
        L.append(pow(i,2)%n)
    for i,j in itertools.permutations(set(L),2):
        t=i-j
        if t<0:
            t+=n
        if t>k:
            t=n-t
        ans[t]+=1
    for i in range(1,k+1):
        print ans[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools

while True:
    n=input()
    if n==0:break
    k=(n-1)/2
    L=[]
    ans=[0]*(k+1)
    for i in range(1,n):
        L.append(pow(i,2)%n)
    for i,j in itertools.combinations(set(L),2):
        t=i-j
        if t<0:
            t+=n
        if t>k:
            t=n-t
        ans[t]+=2
    for i in range(1,k+1):
        print ans[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n=input()
    if n==0:break
    k=(n-1)/2
    ans=[0]*(k+1)
    L=[pow(i,2)%n for i in range(1,n)]
    for i,j in itertools.combinations(set(L),2):
        t=i-j
        if t<0:
            t+=n
        if t>k:
            t=n-t
        ans[t]+=2
    print "\n".join(map(str,ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n=input()
    if n==0:break
    k=(n-1)/2
    ans=[0]*(k+1)
    L=[pow(i,2)%n for i in range(1,n)]
    L=set(L)
    size=len(L)
    L=sorted(L)
    for i in range(size-1):
        for j in range(i+1,size):
            t=L[i]-L[j]
            if t<0:
                t+=n
            if t>k:
                t=n-t
            ans[t]+=2
    print "\n".join(map(str,ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
while True:
    N = input()
    if N == 0:
        break
    ans = [0] * N
    S = set([i * i % N for i in xrange(1, N)])
    for a, b in permutations(S, 2):
        c = a - b
        if c < 0:
            c = c + N
        if c > (N - 1) / 2:
            c = N - c
        ans[c] += 1
    print "\n".join(map(str, ans[1:(N - 1) / 2]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
while True:
    N = input()
    if N == 0:
        break
    ans = [0] * N
    S = set([i * i % N for i in xrange(1, N)])
    for a, b in combinations(S, 2):
        c = a - b
        if c < 0:
            c = c + N
        if c > (N - 1) / 2:
            c = N - c
        ans[c] += 2
    print "\n".join(map(str, ans[1:(N - 1) / 2]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
while True:
    N = int(raw_input())
    if N == 0:
        break
    ans = [0] * N
    S = set([i * i % N for i in xrange(1, N)])
    for a, b in combinations(S, 2):
        c = a - b
        if c < 0:
            c = c + N
        if c > (N - 1) / 2:
            c = N - c
        ans[c] += 2
    print "\n".join(map(str, ans[1:(N - 1) / 2]))

Submission status: Time Limit Exceeded

Solution code:
while True:
    N = int(raw_input())
    if N == 0:
        break
    ans = [0] * N
    L = list(set([i * i % N for i in xrange(1, N)]))
    for i, a in enumerate(L):
        for b in L[i+1:]:
            c = a - b
            if c < 0:
                c = c + N
            if c > (N - 1) / 2:
                c = N - c
            ans[c] += 2
    print "\n".join(map(str, ans[1:(N - 1) / 2]))

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i in range(l):
		for j in range(l):
			d = a[i] - a[j]
			if d < 0:
				d += n
			if d > m:
				d = n - d
			h[d] += 1
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i in range(l):
		for j in range(i+1,l):
			d = a[i] - a[j]
			if d < 0:
				d += n
			if d > m:
				d = n - d
			h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i in range(l):
		ai = a[i]
		for j in range(i+1,l):
			d = ai - a[j]
			if d < 0:
				d += n
			if d > m:
				d = n - d
			h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = i - j
		if d < 0:
			d += n
		if d > m:
			d = n - d
		h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = i - j
		if 0 <= d <= m:
			h[d] += 2
		else:
			if d < 0:
				d += n
			if d > m:
				d = n - d
			h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = sorted(list(set([i**2%n for i in range(1,n)])),reverse = True)
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = i - j
		h[min(d,n-d)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = sorted(list(set([i**2%n for i in range(1,n)])))
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		h[min(j - i,n - j + i)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = sorted(list(set([i**2%n for i in range(1,(n+1)/2)])))
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		h[min(j - i,n - j + i)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools

r = 10001
s = int(r**0.5)
p = [1]*r
p[0] = 0
for i in range(1,s):
	if p[i]:
		p[2*i + 1::i + 1] = [0 for x in range(2*i + 1, r, i + 1)]

while 1:
	n = input()
	if n == 0: break
	m = (n - 1) / 2
	a = sorted(list(set([i**2%n for i in range(1,n)])))
	l = len(a)
	if n%4 == 3 and p[n - 1] == 1:
		for i in range(m):
			print l*(l - 1) / m
		continue
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = j - i
		h[min(d,n - d)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools

r = 10001
s = int(r**0.5)
p = [1]*r
p[0] = 0
for i in range(1,s):
	if p[i]:
		p[2*i + 1::i + 1] = [0 for x in range(2*i + 1, r, i + 1)]

while 1:
	n = input()
	if n == 0: break
	m = (n - 1) / 2
	a = sorted(list(set([i**2%n for i in range(1,n)])))
	l = len(a)
	if n%4 == 3 and p[n - 1] == 1:
		ll = l*(l - 1) / m
		for i in range(m):
			print ll
		continue
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = j - i
		h[min(d,n - d)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Time Limit Exceeded

Solution code:
import itertools

r = 10001
s = int(r**0.5)
p = [1]*r
p[0] = 0
for i in range(1,s):
	if p[i]:
		p[2*i + 1::i + 1] = [0 for x in range(2*i + 1, r, i + 1)]
		
square = [i**2 for i in range(r)]

while 1:
	n = input()
	if n == 0: break
	m = (n - 1) / 2
	a = sorted(list(set([square[i]%n for i in range(1,n)])))
	l = len(a)
	if n%4 == 3 and p[n - 1] == 1:
		ll = l*(l - 1) / m
		for i in range(m):
			print ll
		continue
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = j - i
		h[min(d,n - d)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Memory Limit Exceeded

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_min = 0
	_max = int((n - 1) / 2)

	print(_min, _max)

	ns = set([ x * x % n for x in range(1, n)])
	count  = {}
	for (i, j) in [(i, j) for i in ns for j in ns if i < j]:
		m = i - j
		if m < _min: m = n + m
		if m > _max: m = n - m
		count.setdefault(m, 0)
		count[m] += 1

	for i in range(1, int((n - 1) / 2 + 1)):
		print(count[i] * 2)

Submission status: Memory Limit Exceeded

Solution code:
from itertools import combinations as C

def hoge(tmp, a, b, t, n):
    v = a-b
    if v < 0:
        v = a-b+n
    if v > t:
        v = n-v
    tmp.append(v)

while True:
    n = int(input())
    if n == 0:
        break
    ab = []
    for i in range(1, n):
        ab.append(i**2%n)
    t = (n-1) // 2
    tmp = []
    for p in list(C(set(ab), 2)):
        a, b = p[0], p[1]
        hoge(tmp, a, b, t, n)
        hoge(tmp, b, a, t, n)
    for i in range(1, t+1):
        print(tmp.count(i))

Submission status: Memory Limit Exceeded

Solution code:
from itertools import combinations as C

def hoge(tmp, a, b, t, n):
    v = a-b
    if v < 0:
        v = a-b+n
    if v > t:
        v = n-v
    if v < t+1:
        tmp.append(v)

while True:
    n = int(input())
    if n == 0:
        break
    r = set(pow(i, 2, n) for i in range(1, n))
    t = (n-1) // 2
    tmp = []
    for a, b in C(r, 2):
        hoge(tmp, a, b, t, n)
        hoge(tmp, b, a, t, n)
    for i in range(1, t+1):
        print(tmp.count(i))

Submission status: Accepted

Solution code:
import itertools as it
while 1:
  n = input()
  if n==0: break
  A = sorted(set([pow(i,2,n) for i in range(1,n)]))[::-1]
  C = [0]*n
  for a,b in it.combinations(A,2): C[a-b] += 2
  D = C[::-1]
  for i in range(n/2): print C[i+1]+D[i]

Submission status: Accepted

Solution code:
import itertools as it
while 1:
  n = input()
  if n==0: break
  A = sorted(set([pow(i, 2, n) for i in range(1, n)]))[::-1]
  C=[0]*n
  for a,b in it.combinations(A, 2):
    C[a-b] += 2
  D = C[::-1]
  for i in range(n/2):
    print C[i+1] + D[i]

Submission status: Accepted

Solution code:
import itertools
def func(n):
  rest = {i ** 2 % n for i in range(1, n)}

  count = [0] * n
  for x, y in itertools.combinations(rest, 2):
    count[x - y] += 2

  for i in range(n // 2):
    print(count[i + 1] + count[n - i - 1])


def main():
  while True:
    n = int(input())
    if n == 0:
      break
    func(n)

main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    if N == 1:
        return True
    *S, = set(i**2 % N for i in range(1, N))
    S.sort()
    L = len(S)
    C = [0]*N
    D = [0]*((N-1)//2)
    for i in range(L):
        a = S[i]
        for b in S[:i]:
            C[a - b] += 2
    for i in range(1, N):
        D[min(i, N-i)-1] += C[i]
    write("\n".join(map(str, D)))
    write("\n")
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
import itertools
def func(n):
  rest= {i**2%n for i in range(1,n)}
  count=[0]*n
  for x,y in itertools.combinations(rest,2):
    count[x-y] +=2
  for i in range(n//2):print(count[i+1]+count[n-i-1])
while True:
  n = int(input())
  if n == 0:break
  func(n)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <set>
using namespace std;
const int MAX = 5001;

int main(void){
    int square[MAX];
    for (int i=1; i < MAX+1; i++) square[i-1] = i*i;
    while (true){
        int n;
        cin >> n;
        if (n == 0) break;
        int m = (n-1)/2;
        
        int raw_mod[n-1],mod[m];
        for(int i = 0; i < n-1; i++) raw_mod[i] = square[i]%n;

        sort(raw_mod,raw_mod+n-1);
        mod[0] = raw_mod[0];
        int size;
        for(int i = 1, j = 1; i < n-1; i++){
            if (mod[j-1] != raw_mod[i]){
                mod[j] = raw_mod[i];
                j++;
            }
            size = j;
        }

        int hist[MAX] = {};
        for (int i = 0; i < size-1; i++)
            for (int j = i+1; j < size; j++){
                int tmp1 = mod[i]-mod[j];
                if (tmp1 < 0) tmp1 += n;
                if (tmp1 > m) tmp1 = n-tmp1;
                int tmp2 = mod[j]-mod[i];
                if (tmp2 < 0) tmp2 += n;
                if (tmp2 > m) tmp2 = n-tmp2;
                hist[tmp1-1] += 1;
                hist[tmp2-1] += 1;
            }

        for(int i = 0; i < m; i++)
            cout << hist[i] << endl;
    }
    return 0;    
}

Submission status: Runtime Error

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_min = 0
	_max = int((n - 1) / 2)

	print(_min, _max)

	ns = set([ x * x % n for x in range(1, n)])
	count  = {}
	for i in ns:
	 for j in ns:
	 	if i < j:
			m = i - j
			if m < _min: m = n + m
			if m > _max: m = n - m
			count.setdefault(m, 0)
			count[m] += 1

	for i in range(1, int((n - 1) / 2 + 1)):
		print(count[i] * 2)

Submission status: Runtime Error

Solution code:
# 0142 - Nature of Prime Numbers

while True:
	n = int(input())
	if n == 0: break

	_min = 0
	_max = int((n - 1) / 2)

	print(_min, _max)

	ns = set([ x * x % n for x in range(1, n)])
	count  = {}
	for i in ns:
		for j in ns:
	 		if i < j:
				m = i - j
				if m < _min: m = n + m
				if m > _max: m = n - m
				count.setdefault(m, 0)
				count[m] += 1
	for i in range(1, int((n - 1) / 2 + 1)):
		print(count[i] * 2)

Submission status: Runtime Error

Solution code:
# AOJ 0142 Nature of Prime Numbers
# Python3 2018.6.22 bal4u

MAX = 10000
HALF = 5003

not_prime = [0]*MAX
tbl = [3,  5,  7, 11, 13, 17, 19, 23, 29, 31, \
 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def sieve():
	for i in tbl:
		for j in range(i*i, MAX, i): not_prime[j] = 1
sieve()

while 1:
	n = int(input())
	if n == 0: break
	k = n >> 1
	# 4m+3の素数
	if not_prime[n] == 0 and (n & 3) == 3:
		print(*[k-1]*k, sep='\n')
		continue;

	# 他の奇数についてはまじめに計算
	d = [0]*HALF
	f = [0]*HALF
	a = []
	m = 0;
	for i in range(1, k+1):
		b = i*i % n;
		if f[b] == 0:
			f[b] = 1
			a.append(b)
	for i in range(len(a)):
		for j in range(i):
			b = a[i]-a[j]
			if b == 0: continue
			if b < 0: b += n
			if b > k: b = n-b
			d[b] += 1
	for i in range(1, k+1):	print(d[i]<<1)

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i in range(l):
		for j in range(i+1,l):
			d = a[i] - a[j]
			if d <= m - n:
				d += n
			elif d < 0:
				d *= -1 
			h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i in range(l):
		for j in range(i+1,l):
			d = a[i] - a[j]
			if d < m - n:
				d += n
			elif d < 0:
				d = -d
			h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i in range(l):
		for j in range(i+1,l):
			d = a[i] - a[j]
			if d <= m - n:
				d += n
			elif d < 0:
				d *= -1
			h[d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Runtime Error

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = i - j
		if d < 0:
			d += n
		h[d] += 2 if d <= m else h[n-d] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Runtime Error

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	a = list(set([i**2%n for i in range(1,n)]))
	l = len(a)
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		d = i - j
		if 0 <= d <= m:
			h[d] += 2
		else:
			h[min(d+n,n-d,-d)] += 2
	for i in range(1,m+1):
		print h[i]

Submission status: Runtime Error

Solution code:
import itertools

r = 10001
s = int(r**0.5)
p = [1]*r
p[0] = 0
for i in range(s):
	if p[i]:
		p[2*i+1::i+1] = [0 for i in range(2*i+1,r,i+1)]

while 1:
	n = input()
	if n == 0: break
	m = (n-1)/2
	if p[n-1] == 1:
		for i in range(m):
			print 4
		continue
	a = sorted(list(set([i**2%n for i in range(1,n))))
	h = [0]*(m+1)
	for i,j in itertools.combinations(a,2):
		h[min(j - i,n - j + i)] += 2
	for i in range(1,m+1):
		print h[i]