백준 26073 외로운 곰곰이는 친구가 있어요

 

 

https://www.acmicpc.net/problem/26073

26073번: 외로운 곰곰이는 친구가 있어요

 

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제 및 알아야 되는 정리

https://www.acmicpc.net/problem/9613

9613번: GCD 합

GCD를 구하는 법을 알아봅시다.

 

https://namu.wiki/w/%EB%B2%A0%EC%A3%BC%20%ED%95%AD%EB%93%B1%EC%8B%9D#fn-1

베주 항등식 - 나무위키

베주 항등식을 모르면 풀수없습니다. 공부합시다.

 

 

1. 핵심 아이디어

 

베주 항등식이란 다음과 같습니다.

적어도 둘 중 하나는 0이 아닌 정수 a, b가 있다. 그리고 a와 b의 최대공약수를 d라고 하자. 이때, 다음 세 명제가 성립한다. 1. d= ax+by 를 만족하는 정수 x, y가 반드시 존재한다. 2. d는 정수 x, y에 대하여 ax+by 형태로 표현할 수 있는 가장 작은 자연수이다. 3. 정수 x ,y에 대하여 ax+by 형태로 표현되는 모든 정수는 d의 배수이다.

 

이를 확장해서 생각하면 다음과 같이 정의할수도 있습니다.

적어도 둘 중 하나는 0이 아닌 정수들 A1~An가 있다. 그리고 A1~An의 최대공약수를 d라고 하자. 이때, 다음 세 명제가 성립한다. 1. (d = A1B1+ ... +AnBn)를 만족하는 정수들 B1~Bn가 반드시 존재한다. 2. d는 정수 (A1B1+ ... +AnBn) 형태로 표현할 수 있는 가장 작은 자연수이다. 3. 정수 B1~Bn에 대하여 (A1B1+ ... +AnBn) 형태로 표현되는 모든 정수는 d의 배수이다.

 

즉 입력으로 주어지는 숫자들의 최대공약수(d)는 움직일수 있는 거리의 최소단위라는 뜻이다.

GCD를 사용해서 d를 구하고

X와 Y가 d로 나누어떨어진다면 Ta-da 아니라면 Gave up을 출력하면된다.

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const float INF = 1e10;
const int Dic[8][2] = { {0,1},{0,-1},{1,0},{-1,0} ,{1,1},{-1,-1},{1,-1},{-1,1} };

//////////////////////////////////////////////////////////////////////// 

int GCD(int pA, int pB)
{
	if (pB == 0) 
		return pA;
	else return GCD(pB, pA % pB);
}

int N;


int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> N;
	while(N--)
	{
		int X, Y;
		std::cin >> X >> Y;
		int K;
		std::cin >> K;
		vector<int> A(K);
		for (int i = 0; i < K; i++)
		{
			std::cin >> A[i];
		}

		int v = A[0];
		for (int i = 1; i < K; i++)
		{
			v = GCD(v, A[i]);
		}

		if (X % v == 0 && Y % v == 0)
		{
			std::cout << "Ta-da" << endl;
		}
		else
		{
			std::cout << "Gave up" << endl;
		}
	}
}

 

출처 : 나무위키