제2회 곰곰컵 풀이

A - 치킨댄스를 추는 곰곰이를 본 임스 2 풀이
B - 붙임성 좋은 총총이 풀이
C - 곰곰이와 학식 풀이
D - 오락실에 간 총총이 풀이
E - 곰곰이와 시소 풀이
F - 외로운 곰곰이는 친구가 있어요 풀이
G - 곰곰이와 테트리스 풀이
H - 곰곰아 선 넘지마 풀이
I - 곰곰이의 식단 관리 2 풀이
J - 서커스 나이트 풀이

BOJ 26073 - 외로운 곰곰이는 친구가 있어요 링크
(2022.12.01 기준 G3)

문제

친구 N명이 있고, 각 i번째 친구는 Xi, Yi에 위치해 있고, 이동할 수 있는 거리 Aij가 K개가 있다.
곰곰이가 (0, 0)에 있다면 곰곰이한테 갈 수 있는지 각 친구마다 판정

알고리즘

베주 항등식

풀이

출처 제2회 곰곰컵 공식 해설

결국, 모든 이동 가능한 거리의 최대 공약수 d를 구해서, d가 각 X, Y를 나머지 없이 나눌 수 있는지 확인하는 문제다.

......... 음.. 뭐.. 그렇다.
Do you know? 문제다.
모르면 못푼다... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ큐ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ (나도 대회 때 못풀었음)

이제라도 꼭 알아두자! 절대 잊지 못할 정수론인 듯.

코드

import sys; input = sys.stdin.readline
from math import gcd

for _ in range(int(input())):
    X, Y = map(int, input().split())
    K, *A = map(int, input().split())

    # 베주 항등식 이용
    # 이동 가능한 모든 거리의 최대 공약수를 구하여
    # X와 Y를 딱 나눌 수 있는지 확인

    a = A[0]
    for i in range(1, K):
        a = gcd(a, A[i])
        if a == 1: # 1이 나왔다면 더 이상 진행할 필요가 없다.
            print('Ta-da')
            break
    else:
        print('Ta-da') if not X % a and not Y % a else print('Gave up')