#yukicoder 2797 Square Tile import random, math #愚直判定 def check(A, B, A_list, B_list): L = A ** 2 + B ** 2 if not len(A_list) == len(B_list) == L: return False if not all(i in range(L) and j in range(L) for i, j in A_list + B_list): return False D = [[0] * L for _ in range(L)] for i, j in A_list: for x in range(i, i + A): x %= L for y in range(j, j + A): y %= L if D[x][y] == 1: return False D[x][y] = 1 for i, j in B_list: for x in range(i, i + B): x %= L for y in range(j, j + B): y %= L if D[x][y] == 1: return False D[x][y] = 1 return True #タイルA_listが定められていると仮定する。B_listを愚直に作成せよ。 def fill(A, B, A_list): L = A ** 2 + B ** 2 if not len(A_list) == L: return [] if not all(i in range(L) and j in range(L) for i, j in A_list): return [] D = [[0] * L for _ in range(L)] for i, j in A_list: for x in range(i, i + A): x %= L for y in range(j, j + A): y %= L if D[x][y] == 1: return [] D[x][y] = 1 B_list = [] while len(B_list) < L: for i in range(L): for j in range(L): if D[i][j] == 0 and D[(i - 1) % L][j] == D[i][(j - 1) % L] == 1: B_list.append((i, j)) for x in range(i, i + B): x %= L for y in range(j, j + B): y %= L if D[x][y] == 1: return [] D[x][y] = 1 return B_list #乱択解法 def solve_random(A, B): L = A ** 2 + B ** 2 while True: A_list = [(random.randint(0, L - 1), random.randint(0, L - 1)) for _ in range(L - 1)] + [(0, 0)] B_list = fill(A, B, A_list) if len(B_list) == L: assert check(A, B, A_list, B_list) visualize(A, B, A_list, B_list) return A_list, B_list def visualize(A, B, A_list, B_list): L = A ** 2 + B ** 2 D = [[None] * L for _ in range(L)] for i, j in A_list: for x in range(i, i + A): x %= L for y in range(j, j + A): y %= L D[x][y] = 'a' D[i][j] = 'A' for i, j in B_list: for x in range(i, i + B): x %= L for y in range(j, j + B): y %= L D[x][y] = 'b' D[i][j] = 'B' for d in D: print(''.join(d)) #実験結果を採用 #答えとなる盤面を出力せよ。 def solve(A, B): L = A ** 2 + B ** 2 if math.gcd(A, B) == 1: A_list = [] B_list = [] for i in range(L): A_list.append((A * i % L, B * i % L)) B_list.append((A * (i + 1) % L, B * i % L)) return A_list, B_list else: G = math.gcd(A, B) H = L // G a_list, b_list = solve(A // G, B // G) A_list = [(H * i + G * x, H * j + G * y) for x, y in a_list for i in range(G) for j in range(G)] B_list = [(H * i + G * x, H * j + G * y) for x, y in b_list for i in range(G) for j in range(G)] return A_list, B_list def test(A, B): A_list, B_list = solve(A, B) visualize(A, B, A_list, B_list) #答えを実行 A, B = map(int, input().split()) A_list, B_list = solve(A, B) for i, j in A_list + B_list: print(i, j)