둥근 탁자에 의자 n개가 빙 둘러 놓여 있고, 시계 방향으로 0번부터 n−1번까지 번호가 붙어 있다.
n−1번 의자에서 시계 방향으로 한 칸 가면 0번 의자다.
먼저 0번 의자에 사탕을 하나 놓는다.
그다음부터는 방금 사탕을 놓은 의자에서 시계 방향으로 k칸 간 의자에 사탕을 하나 놓는다.
가서 닿은 의자에 이미 사탕이 있으면 사탕을 놓지 않고 멈춘다.
n과 k의 최대공약수를 g라 하면, 멈췄을 때 사탕이 놓여 있는 의자는 번호가 g의 배수인 의자 전부라는 사실이 알려져 있다(0도 g의 배수로 친다).
한 줄에 n과 k가 빈칸 하나로 띄워 주어진다.
사탕이 놓인 의자의 수와, 사탕이 놓인 의자의 번호 가운데 가장 큰 것을 이 차례로 빈칸 하나로 띄워 한 줄에 출력하라.
입력
1 ≤ n ≤ 1,000,000,000, 1 ≤ k ≤ 1,000,000,000(정수이고, 쉼표 없이 숫자만 주어진다). k는 n보다 클 수도 있다
출력
사탕이 놓인 의자의 수와 그 가운데 가장 큰 번호를 빈칸 하나로 띄운 한 줄
예시 1 · stdin
12 8
stdout
3 8
예시 2 · stdin
5 10
stdout
1 0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
최대공약수를 구하는 함수가 있는 언어와 없는 언어가 있어요. Python은 math.gcd(n, k), C++은 <numeric>의 std::gcd(n, k)(C++17부터)를 바로 써요. JS·TS·C·크레이콘에는 없고, Java와 C#에는 큰 수 타입의 것(BigInteger.gcd, BigInteger.GreatestCommonDivisor)만 있어서 int에는 보통 직접 만들어요. 만드는 방법은 유클리드 호제법이에요. b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾸면 남은 a가 최대공약수예요. 첫째 함정은 이 바꾸기의 차례예요. a = b; b = a % b;라고 쓰면 a가 이미 b로 바뀐 뒤라 b % b = 0이 되고, 늘 k가 최대공약수로 나와요. 예시 1은 1 4가 돼요. 나머지를 임시 변수에 먼저 담거나, Python a, b = b, a % b, JS·TS [a, b] = [b, a % b], C# (a, b) = (b, a % b)처럼 한꺼번에 바꿔요. 둘째 함정은 나머지 대신 빼기를 되풀이하는 것이에요. 1000000000 1이나 1 1000000000 같은 입력에서 10억 번쯤 빼야 해서 시간 안에 끝나지 않아요. 나머지를 쓰면 이 범위의 어떤 입력도 몇십 번 안에 끝나요. 셋째 함정은 최대공약수 없이 k로 바로 계산하는 것이에요. 예시 1에서 12를 8로 나눈 몫 1과 12 − 8 = 4가 나오지만 답은 3 8이에요. 넷째 함정은 Python의 /예요. n / g는 나누어떨어져도 실수라서 예시 1에서 3.0 8이 찍혀요. 몫은 n // g로 구해요. JS·TS와 크레이콘의 /도 소수까지 나누지만 값이 정수이면 3으로 찍혀요. 크레이콘에서 몫은 수학.몫(n, g)으로 구해요.
Pythonmain.py · 6 줄
import mathn, k = map(int, input().split())g = math.gcd(n, k)# //는 몫(정수)이다. /를 쓰면 3.0처럼 실수가 된다print(n // g, n - g)
JavaScriptmain.js · 9 줄
const [n, k] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다let a = n;let b = k;while (b !== 0) { [a, b] = [b, a % b];}const g = a;console.log(`${n / g} ${n - g}`);
TypeScriptmain.ts · 10 줄
import { readFileSync } from "node:fs";const [n, k]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다let a: number = n;let b: number = k;while (b !== 0) { [a, b] = [b, a % b];}const g: number = a;console.log(`${n / g} ${n - g}`);
JavaMain.java · 19 줄
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); // 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다 int a = n; int b = k; while (b != 0) { int r = a % b; // 나머지를 먼저 담아 둔다 a = b; b = r; } int g = a; System.out.println((n / g) + " " + (n - g)); }}
C#Main.cs · 20 줄
using System;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]); int k = int.Parse(p[1]); // 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다 int a = n; int b = k; while (b != 0) { (a, b) = (b, a % b); } int g = a; Console.WriteLine($"{n / g} {n - g}"); }}
C++main.cpp · 9 줄
#include <iostream>#include <numeric>int main() { int n, k; std::cin >> n >> k; int g = std::gcd(n, k); // <numeric>, C++17부터 std::cout << n / g << " " << n - g << "\n";}
Cmain.c · 16 줄
#include <stdio.h>int main(void) { int n, k; scanf("%d %d", &n, &k); /* 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다 */ int a = n, b = k; while (b != 0) { int r = a % b; /* 나머지를 먼저 담아 둔다 */ a = b; b = r; } int g = a; printf("%d %d\n", n / g, n - g); return 0;}
Craykonmain.cray · 14 줄
수들 = 콘솔.수들읽기();n = 수들[0];k = 수들[1];// 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다a = n;b = k;동안 (b != 0){ r = a % b; // 나머지를 먼저 담아 둔다 a = b; b = r;}g = a;콘솔.쓰기(수학.몫(n, g) + " " + (n - g));