GCDP0313

Candies placed every k seats around a round table

There are n chairs around a round table, numbered 0 to n−1 clockwise. One step clockwise from chair n−1 is chair 0. First put one candy on chair 0. After that, keep putting one candy on the chair k steps clockwise from the chair where you just put a candy. If the chair you arrive at already has a candy, put nothing there and stop. Let g be the greatest common divisor of n and k; it is known that when you stop, the chairs holding a candy are exactly all the chairs whose number is a multiple of g (0 counts as a multiple of g). One line gives n and k separated by one space. Print the number of chairs holding a candy and the largest number among those chairs, in this order, on one line separated by one space.

Input: 1 ≤ n ≤ 1,000,000,000, 1 ≤ k ≤ 1,000,000,000 (integers, given as digits only without commas).
k may be larger than n
Output: One line with the number of chairs holding a candy and the largest such chair number, separated by one space

Example 1 · stdin

12 8

stdout

3 8

Example 2 · stdin

5 10

stdout

1 0

main.py Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Some languages have a GCD function and some do not.
Python has math.gcd(n, k) and C++ has std::gcd(n, k) in <numeric> (since C++17).
JS, TS, C and Craykon have none, and Java and C# only have one for big-number types (BigInteger.gcd, BigInteger.GreatestCommonDivisor), so for int you usually write it yourself.
The way to write it is Euclid's algorithm.
Replace (a, b) with (b, a % b) until b is 0; the a that remains is the GCD.
The first trap is the order of that replacement.
With a = b; b = a % b; a has already become b, so you compute b % b = 0 and the GCD always comes out as k.
Example 1 becomes 1 4.
Store the remainder in a temporary first, or replace both at once as in Python a, b = b, a % b, JS/TS [a, b] = [b, a % b], C# (a, b) = (b, a % b).
The second trap is repeating subtraction instead of taking the remainder.
On inputs such as 1000000000 1 or 1 1000000000 it needs about a billion subtractions and does not finish in time.
With the remainder, every input in this range finishes within a few dozen steps.
The third trap is computing with k directly, without the GCD.
On example 1 you get the quotient of 12 by 8, which is 1, and 12 − 8 = 4, but the answer is 3 8.
The fourth trap is Python's /.
n / g is a float even when it divides evenly, so example 1 prints 3.0 8.
Use n // g for the quotient.
/ in JS, TS and Craykon also divides into decimals, but a whole value is printed as 3.
In Craykon the quotient is Mathf.Quot(n, g).

Pythonmain.py · 6 lines

import math n, k = map(int, input().split())g = math.gcd(n, k)# //는 몫(정수)이다. /를 쓰면 3.0처럼 실수가 된다print(n // g, n - g)

JavaScriptmain.js · 9 lines

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 lines

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 lines

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 lines

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 lines

#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 lines

#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 lines

수들 = Console.ReadNumbers();n = 수들[0];k = 수들[1];// 유클리드 호제법: b가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾼다a = n;b = k;while (b != 0){    r = a % b; // 나머지를 먼저 담아 둔다    a = b;    b = r;}g = a;Console.WriteLine(Mathf.Quot(n, g) + " " + (n - g));