1850번: 최대공약수
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}}} |
| {{{...}}} | {{{...}}} | {{{...}}} | {{{...}}} |
#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)}}}의 구현까지 포함한 예시 정답 코드는 다음과 같습니다.
- C++
#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;
}
- Python
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 |