1850번: 최대공약수

[접기]

목차

  • 1. 문제
  • 2. 입력
  • 3. 출력
  • 4. 예제 입출력
  • 5. 풀이
  • 6. 예시 코드
  • 7. 테스트 케이스


1. 문제


[틀:백준(번호=1850, 분류=수학, 제목=최대공약수, 시간제한=2초, 메모리제한=128MB]

본문은 백준 온라인 저지에서 확인할 수 있습니다.

2. 입력


첫째 줄에 두 자연수 {{{A}}}와 {{{B}}}를 이루는 {{{1}}}의 개수가 주어진다. 입력되는 수는 {{{263}}}보다 작은 자연수이다.

3. 출력


첫째 줄에 {{{A}}}와 {{{B}}}의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

4. 예제 입출력


예제 입력 1 예제 출력 1
3 4 1

예제 입력 2 예제 출력 2
3 6 111

예제 입력 3 예제 출력 3
500000000000000000 500000000000000002 11

5. 풀이


모든 자리가 {{{1}}}로만 구성된 수를 두 개 주고, 이들의 최대공약수를 구하는 문제입니다. 모든 자리가 {{{1}}}로만 구성되었다는 것은 {{{111}}}, {{{1111}}}, {{{11111}}}과 같이 {{{1}}}만 주욱 늘어놓은 숫자들이라는 의미입니다. 숫자가 매우 길어질 수 있으므로 실제론 각 숫자의 자릿수만을 입력으로 줍니다. 예를 들어, 첫 번째 예제 입력인 {{{3 4}}}는 {{{111}}}과 {{{1111}}}의 최소공배수를 찾으라는 의미입니다.

수가 작다면 원래 숫자로 복원한 뒤에 일반적인 최대공약수 구하는 방법을 사용할 수 있습니다. 최대공약수는 일단 {{{gcd(a, b)}}}라는 함수를 통해 구할 수 있다고 가정해봅시다. 그렇다면 다음과 같은 코드를 작성해볼 수 있습니다. 코드는 통일성을 위해 C++로 작성하였습니다.


#include

int gcd(int a, int b) {
// gcd 구현
return ???;
}

int main() {
int a, b;
scanf("%d %d", &a, &b);
int real_a = 0, real_b = 0;
for (int i = 0; i < a; i++)
real_b = real_a * 10 + 1;
for (int i = 0; i < b; i++)
real_b = real_b * 10 + 1;
int ans = gcd(real_a, real_b);
printf("%d", ans);
return 0;
}

그러나 수가 작다고 하더라도 {{{real_a}}}와 {{{real_b}}}를 구하는 과정은 약간 비효율적으로 느껴집니다. {{{1}}}로만 구성된 숫자들은 누가 봐도 규칙적이므로 무언가 수식을 통해 나타낼 수 있지 않을까하는 생각을 해볼 수 있습니다. 사실 모든 숫자들에 {{{9}}}를 곱해보면 좀 더 명확하게 식으로 나타내어질 법한 규칙이 보입니다.
{{{n}}} {{{1}}}이 {{{n}}}개 {{{x9}}} {{{10n}}}
{{{1}}} {{{1}}} {{{9}}} {{{10}}}
{{{2}}} {{{11}}} {{{99}}} {{{100}}}
{{{3}}} {{{111}}} {{{999}}} {{{1000}}}
{{{4}}} {{{1111}}} {{{9999}}} {{{10000}}}
{{{5}}} {{{11111}}} {{{99999}}} {{{100000}}}
{{{...}}} {{{...}}} {{{...}}} {{{...}}}
즉, {{{1}}}이 {{{n}}}개 있는 수는 {{{(10n-1)/9}}}이라는 것을 알 수 있습니다. 이를 이용해 방금 짠 프로그램을 조금 더 빠르게 바꿔봅시다. {{{pow(a, n)}}}이라는 함수 또한 미리 만들어져 있다고 가정합시다. 실제로 {{{an}}}은 {{{O(log n)}}}시간 내에 구할 수 있습니다.


#include

int gcd(int a, int b) {
// gcd 구현
return ???;
}

int pow(int a, int n) {
// pow 구현
return ???;
}

int main() {
int a, b;
scanf("%d %d", &a, &b);
int real_a = (pow(10, a) - 1) / 9;
int real_b = (pow(10, b) - 1) / 9;
int ans = gcd(real_a, real_b);
printf("%d", ans);
return 0;
}

그러나 이는 여전히 느린 방법입니다. 여기에 10의 거듭제곱을 미리 전처리 해두거나 해서 아무리 거듭제곱을 빠르게 계산하더라도 결국 최소공배수를 구하는 데 매우 오랜 시간이 걸립니다. 왜냐하면 입력으로 주어지는 수가 {{{2^63}}}까지인데, 그렇다는 말은 실제로 주어지는 수는 상상하기 힘들 정도로 커진다는 것입니다.

그런데, 사실 우리가 실제로 주어진 수들을 식으로 표현했으니 두 수의 최대공약수까지 수학으로 계산해버리면 됩니다. 실제로, 두 수의 최대공약수 또한 {{{(10n-1)/9}}} 꼴이어야 한다는 것은 쉽게 증명할 수 있습니다. 그러면 {{{(10a-1)/9}}}이 {{{(10b-1)/9}}}를 나눈다는 것과 {{{a}}}이 {{{b}}}를 나눈다는 것이 동치라는 것까지 증명할 수 있습니다. 따라서 그냥 주어진 {{{a}}}와 {{{b}}}의 최대공약수가 {{{d}}}라면 우리는 {{{(10d-1)/9}}}, 즉, {{{d}}}개의 {{{1}}}을 출력하면 됩니다. 코드로 나타내면 다음과 같습니다.


#include

int gcd(int a, int b) {
// gcd 구현
return ???;
}

int main() {
int a, b;
scanf("%d %d", &a, &b);
int d = gcd(a, b);
for (int i = 0; i < d; i++)
printf("1");
return 0;
}

그러나 여기에서 하나 주의할 점은 입력이 {{{int}}}범위를 벗어날 수 있다는 것입니다. 따라서 {{{long long}}}을 사용해야 모든 테스트케이스를 통과할 수 있습니다.


#include

long long gcd(long long a, long long b) {
// gcd 구현
return ???;
}

int main() {
long long a, b;
scanf("%lld %lld", &a, &b);
long long d = gcd(a, b);
for (int i = 0; i < d; i++)
printf("1");
return 0;
}

6. 예시 코드


실제로 {{{gcd(a, b)}}}의 구현까지 포함한 예시 정답 코드는 다음과 같습니다.


#include

long long gcd(long long a, long long b) {
long long t = 1;
while b != 0:
t = a % b;
a = b;
b = t;
return a;
}

int main() {
long long a, b;
scanf("%lld %lld", &a, &b);
long long d = gcd(a, b);
for (int i = 0; i < d; i++)
printf("1");
return 0;
}


a,b=map(int,input().split())
while b:a,b=b,a%b
print('1'*a)

7. 테스트 케이스


예제 입력 4 예제 출력 4
1 1 1

예제 입력 5 예제 출력 5
9 12 111

예제 입력 6 예제 출력 6
18 12 111111

예제 입력 7 예제 출력 7
11 17 1

예제 입력 8 예제 출력 8
11 1 11111111111

예제 입력 9 예제 출력 9
1152921504606846976 1152921504606846977 1