최대공약수함수 만들기넘침(오버플로)P0037

최대공약수와 최소공배수

두 자연수 a, b가 빈칸으로 나뉘어 한 줄에 주어진다.
a와 b의 최대공약수와 최소공배수를 빈칸 하나로 나누어 한 줄에 출력하라.

입력: 1 ≤ a, b ≤ 10^12.
최소공배수는 10^15를 넘지 않는다.
출력: 최대공약수 최소공배수

예시 1 · stdin

12 18

stdout

6 36

예시 2 · stdin

987000000000 977000000000

stdout

1000000000 964299000000000

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

최대공약수는 유클리드 호제법(a, b = b, a % b를 b가 0이 될 때까지)으로 구하고, 최소공배수는 a / g * b처럼 먼저 나누고 나중에 곱해야 해요.
a * b / g로 곱부터 하면 예시 2에서 a*b ≈ 9.6×10^23이 되어 C·C++·Java·C#의 64비트 long(약 9.2×10^18)이 넘치고, JavaScript·TypeScript·크레이콘은 2^53을 넘어 끝자리가 틀려요.
Python만 정수 크기에 끝이 없어 어느 쪽도 맞아요.
10^12는 32비트 int(약 21억)에 들어가지 않으니 C 계열은 처음부터 long/long long으로 받아요.
이미 있는 함수: Python math.gcd, C++ std::gcd(<numeric>), C# BigInteger.GreatestCommonDivisor.
크레이콘은 최대공약수(a, b) { … 돌려주기 a; }로 함수를 만들고, /가 소수까지 나누므로 몫은 수학.몫(a, g)로 구해요.

Pythonmain.py · 9 줄

def gcd(a, b):    while b:        a, b = b, a % b    return a  a, b = map(int, input().split())g = gcd(a, b)print(g, a // g * b)

JavaScriptmain.js · 9 줄

const [a, b] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); function gcd(a, b) {  while (b !== 0) [a, b] = [b, a % b];  return a;} const g = gcd(a, b);console.log(`${g} ${(a / g) * b}`);

TypeScriptmain.ts · 10 줄

import { readFileSync } from "node:fs";const [a, b]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); function gcd(a: number, b: number): number {  while (b !== 0) [a, b] = [b, a % b];  return a;} const g = gcd(a, b);console.log(`${g} ${(a / g) * b}`);

JavaMain.java · 19 줄

import java.util.Scanner; public class Main {    static long gcd(long a, long b) {        while (b != 0) {            long t = a % b;            a = b;            b = t;        }        return a;    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        long a = sc.nextLong(), b = sc.nextLong();        long g = gcd(a, b);        System.out.println(g + " " + (a / g * b));    }}

C#Main.cs · 20 줄

using System; class Program{    static long Gcd(long a, long b)    {        while (b != 0)        {            (a, b) = (b, a % b);        }        return a;    }     static void Main()    {        long[] v = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse);        long g = Gcd(v[0], v[1]);        Console.WriteLine($"{g} {v[0] / g * v[1]}");    }}

C++main.cpp · 9 줄

#include <iostream>#include <numeric> int main() {    long long a, b;    std::cin >> a >> b;    long long g = std::gcd(a, b);    std::cout << g << ' ' << a / g * b << '\n';}

Cmain.c · 18 줄

#include <stdio.h> long long gcd(long long a, long long b) {    while (b != 0) {        long long t = a % b;        a = b;        b = t;    }    return a;} int main(void) {    long long a, b;    scanf("%lld %lld", &a, &b);    long long g = gcd(a, b);    printf("%lld %lld\n", g, a / g * b);    return 0;}

Craykonmain.cray · 16 줄

최대공약수(a, b){    동안 (b != 0)    {        t = a % b;        a = b;        b = t;    }    돌려주기 a;} 수들 = 콘솔.수들읽기();a = 수들[0];b = 수들[1];g = 최대공약수(a, b);콘솔.쓰기(g + " " + 수학.몫(a, g) * b);