丸いテーブルのまわりに椅子が 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()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
最大公約数を求める関数がある言語とない言語があります。 Python は math.gcd(n, k)、C++ は <numeric> の std::gcd(n, k)（C++17 から）をそのまま使います。 JS・TS・C・Craykon にはなく、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 と Craykon の / も小数まで割りますが、値が整数なら 3 と出ます。 Craykon では商を 数学.商(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));