[BOJ 17586 // C++] Diagonal Cut

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17586번 문제인 Diagonal Cut이다.
문제는 아래 링크를 확인하자.

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

 

정사각형을 이등분하는 직선은 항상 그 정사각형의 중심을 지나야하므로, 주어진 초콜릿블록을 지나는 대각선이 지나는 칸 중, 정가운데를 지나는 칸의 개수를 세는 것으로 문제를 해결할 수 있다.

 

주어지는 대각선은 두 변의 최대공약수 횟수만큼 같은 규칙으로 칸을 지나고, 서로소인 두 정수를 변의 길이로 갖는 직사각형에서 대각선이 어떤 칸의 정중앙을 지나려면 두 변의 길이가 모두 홀수여야 함을 관찰해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y) return gcd(y, x % y);
	return x;
}	
ll A, B, G;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B;
	G = gcd(A, B);
	A /= G, B /= G;
	if ((A & 1) && (B & 1)) cout << G;
	else cout << 0;
}