この切り方はユークリッドの互除法を絵にしたものです。 横 w が縦 h 以上なら一辺 h のかけらが「w を h で割った商」個でき、残る横は w % h です。 だから、かけらの数は互除法に出てくる商をすべて足した値で、最後に残る最も小さいかけらの一辺が a と b の最大公約数です。 Python math.gcd、C++ std::gcd（<numeric>）は最大公約数だけを返して商は教えてくれないので、ここでは while (y != 0) の繰り返しを自分で書きます（Java・C#・C・JavaScript・TypeScript・Craykon には整数用の gcd 関数がないので、どのみち自分で書きます）。 質問には、同じ繰り返しを回しながら、残った紙の左と上にすでに切り取られた長さ left、top と、これまでに切ったかけらの数 count を一緒に持っていきます。 横に切る段階で c - left が k × h 以下ならその段階のかけらで、番号は count +（c - left - 1 を h で割った商）+ 1 です。 縦に切る段階は r と top で同じようにします。 商は Python //、Java・C#・C・C++ の整数の / で求めます。 JavaScript・TypeScript の / は小数まで割るので (w - w % h) / h や Math.floor(w / h) で、Craykon も / が小数まで割るので 数学.商(w, h) で求めます。 罠その一：かけらを一つずつ切って数えると（余りの代わりに引き算）、例 2 の横 10^15、縦 1 の紙で 10^15 回まわります。 どの言語でも時間内に終わらないので、同じ大きさのかけら k 個を一度に飛ばさなければなりません。 そうすれば段階は 100 回を超えません。 罠その二：番号を （c - left を h で割った商）+ 1 で求めると、かけらの最後のマスが次のかけらに入ってしまいます。 例 1 の 7 番のマス、7 番の行は 1 番のかけらですが、2 が出ます。 罠その三：切り取られた長さを引かずに最初の紙の c、r をそのまま使うと、例 1 の 9 番のマス、7 番の行ではどの段階にも入らず、残った紙がなくなって 0 で割ることになります。 答えは 5 番のかけらです。 罠その四：長さも、かけらの数も 10^15 まで大きくなります。 Java・C#・C・C++ は long/long long を使わなければなりません。 Java でかけらの数を int で数えると、例 2 の一行目が -1530494976 と出ます。 Python の整数には大きさの制限がなく、JavaScript・TypeScript・Craykon の数は 2^53（約 9 × 10^15）まで正確なので、この範囲はそのままで合います。
Pythonmain.py · 46 行
import sysdef count_and_smallest(a, b): """조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수).""" count = 0 while b != 0: count += a // b # 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 a, b = b, a % b return count, adef find(a, b, c, r): """c번 칸, r번 줄이 든 조각의 번호와 한 변.""" left = top = 0 # 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 w, h = a, b # 남은 종이의 가로와 세로 count = 0 # 지금까지 잘라 낸 조각의 수 while True: if w >= h: # 왼쪽에서 h × h 조각을 k개 잘라 낸다 k = w // h if c - left <= k * h: return count + (c - left - 1) // h + 1, h count += k left += k * h w -= k * h else: # 위쪽에서 w × w 조각을 k개 잘라 낸다 k = h // w if r - top <= k * w: return count + (r - top - 1) // w + 1, w count += k top += k * w h -= k * wdef main(): data = sys.stdin.read().split() a, b, q = int(data[0]), int(data[1]), int(data[2]) total, smallest = count_and_smallest(max(a, b), min(a, b)) out = [f"{total} {smallest}"] for i in range(q): number, side = find(a, b, int(data[3 + 2 * i]), int(data[4 + 2 * i])) out.append(f"{number} {side}") print("\n".join(out))main()
JavaScriptmain.js · 45 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 몫. 값이 2^53 안의 정수라 나머지를 먼저 빼면 나눗셈이 딱 떨어진다const div = (x, y) => (x - (x % y)) / y;// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)function countAndSmallest(a, b) { let count = 0; while (b !== 0) { count += div(a, b); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 [a, b] = [b, a % b]; } return [count, a];}// c번 칸, r번 줄이 든 조각의 [번호, 한 변]function find(a, b, c, r) { let left = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 let top = 0; let w = a; // 남은 종이의 가로와 세로 let h = b; let count = 0; // 지금까지 잘라 낸 조각의 수 for (;;) { if (w >= h) { const k = div(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 if (c - left <= k * h) return [count + div(c - left - 1, h) + 1, h]; count += k; left += k * h; w -= k * h; } else { const k = div(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 if (r - top <= k * w) return [count + div(r - top - 1, w) + 1, w]; count += k; top += k * w; h -= k * w; } }}const [a, b, q] = data;const out = [countAndSmallest(Math.max(a, b), Math.min(a, b)).join(" ")];for (let i = 0; i < q; i++) { out.push(find(a, b, data[3 + 2 * i], data[4 + 2 * i]).join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 46 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 몫. 값이 2^53 안의 정수라 나머지를 먼저 빼면 나눗셈이 딱 떨어진다const div = (x: number, y: number): number => (x - (x % y)) / y;// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)function countAndSmallest(a: number, b: number): [number, number] { let count = 0; while (b !== 0) { count += div(a, b); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 [a, b] = [b, a % b]; } return [count, a];}// c번 칸, r번 줄이 든 조각의 [번호, 한 변]function find(a: number, b: number, c: number, r: number): [number, number] { let left = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 let top = 0; let w = a; // 남은 종이의 가로와 세로 let h = b; let count = 0; // 지금까지 잘라 낸 조각의 수 for (;;) { if (w >= h) { const k = div(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 if (c - left <= k * h) return [count + div(c - left - 1, h) + 1, h]; count += k; left += k * h; w -= k * h; } else { const k = div(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 if (r - top <= k * w) return [count + div(r - top - 1, w) + 1, w]; count += k; top += k * w; h -= k * w; } }}const [a, b, q] = data;const out: string[] = [countAndSmallest(Math.max(a, b), Math.min(a, b)).join(" ")];for (let i = 0; i < q; i++) { out.push(find(a, b, data[3 + 2 * i], data[4 + 2 * i]).join(" "));}console.log(out.join("\n"));
JavaMain.java · 54 行
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); int q = Integer.parseInt(st.nextToken()); StringBuilder out = new StringBuilder(); // 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수) long x = Math.max(a, b), y = Math.min(a, b), total = 0; while (y != 0) { total += x / y; // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 long t = x % y; x = y; y = t; } out.append(total).append(' ').append(x).append('\n'); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); long c = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); long left = 0, top = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 long w = a, h = b; // 남은 종이의 가로와 세로 long count = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) { // 왼쪽에서 h × h 조각을 k개 잘라 낸다 long k = w / h; if (c - left <= k * h) { out.append(count + (c - left - 1) / h + 1).append(' ').append(h).append('\n'); break; } count += k; left += k * h; w -= k * h; } else { // 위쪽에서 w × w 조각을 k개 잘라 낸다 long k = h / w; if (r - top <= k * w) { out.append(count + (r - top - 1) / w + 1).append(' ').append(w).append('\n'); break; } count += k; top += k * w; h -= k * w; } } } System.out.print(out); }}
C#Main.cs · 59 行
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long a = long.Parse(p[0]), b = long.Parse(p[1]); int q = int.Parse(p[2]); var sb = new StringBuilder(); // 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수) long x = Math.Max(a, b), y = Math.Min(a, b), total = 0; while (y != 0) { total += x / y; // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 (x, y) = (y, x % y); } sb.Append(total).Append(' ').Append(x).Append('\n'); for (int i = 0; i < q; i++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long c = long.Parse(p[0]), r = long.Parse(p[1]); long left = 0, top = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 long w = a, h = b; // 남은 종이의 가로와 세로 long count = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) // 왼쪽에서 h × h 조각을 k개 잘라 낸다 { long k = w / h; if (c - left <= k * h) { sb.Append(count + (c - left - 1) / h + 1).Append(' ').Append(h).Append('\n'); break; } count += k; left += k * h; w -= k * h; } else // 위쪽에서 w × w 조각을 k개 잘라 낸다 { long k = h / w; if (r - top <= k * w) { sb.Append(count + (r - top - 1) / w + 1).Append(' ').Append(w).Append('\n'); break; } count += k; top += k * w; h -= k * w; } } } Console.Write(sb); }}
C++main.cpp · 53 行
#include <algorithm>#include <iostream>#include <numeric>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long a, b; int q; cin >> a >> b >> q; // 조각의 수: 유클리드 호제법의 몫을 모두 더한 값 long long x = max(a, b), y = min(a, b), total = 0; while (y != 0) { total += x / y; // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 long long t = x % y; x = y; y = t; } // 가장 작은 조각의 한 변은 최대공약수다(x와 같다) cout << total << ' ' << gcd(a, b) << '\n'; while (q--) { long long c, r; cin >> c >> r; long long left = 0, top = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 long long w = a, h = b; // 남은 종이의 가로와 세로 long long count = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) { // 왼쪽에서 h × h 조각을 k개 잘라 낸다 long long k = w / h; if (c - left <= k * h) { cout << count + (c - left - 1) / h + 1 << ' ' << h << '\n'; break; } count += k; left += k * h; w -= k * h; } else { // 위쪽에서 w × w 조각을 k개 잘라 낸다 long long k = h / w; if (r - top <= k * w) { cout << count + (r - top - 1) / w + 1 << ' ' << w << '\n'; break; } count += k; top += k * w; h -= k * w; } } } return 0;}
Cmain.c · 47 行
#include <stdio.h>int main(void) { long long a, b; int q; if (scanf("%lld %lld %d", &a, &b, &q) != 3) return 0; /* 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수) */ long long x = a > b ? a : b, y = a > b ? b : a, total = 0; while (y != 0) { total += x / y; /* 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 */ long long t = x % y; x = y; y = t; } printf("%lld %lld\n", total, x); for (int i = 0; i < q; i++) { long long c, r; if (scanf("%lld %lld", &c, &r) != 2) return 0; long long left = 0, top = 0; /* 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 */ long long w = a, h = b; /* 남은 종이의 가로와 세로 */ long long count = 0; /* 지금까지 잘라 낸 조각의 수 */ for (;;) { if (w >= h) { /* 왼쪽에서 h × h 조각을 k개 잘라 낸다 */ long long k = w / h; if (c - left <= k * h) { printf("%lld %lld\n", count + (c - left - 1) / h + 1, h); break; } count += k; left += k * h; w -= k * h; } else { /* 위쪽에서 w × w 조각을 k개 잘라 낸다 */ long long k = h / w; if (r - top <= k * w) { printf("%lld %lld\n", count + (r - top - 1) / w + 1, w); break; } count += k; top += k * w; h -= k * w; } } } return 0;}
Craykonmain.cray · 59 行
첫줄 = コンソール.数読み();a = 첫줄[0];b = 첫줄[1];q = 첫줄[2];// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)x = 数学.大きい方(a, b);y = 数学.小さい方(a, b);모두 = 0;間 (y != 0){ 모두 = 모두 + 数学.商(x, y); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 t = x % y; x = y; y = t;}コンソール.書く(모두 + " " + x);// c번 칸, r번 줄이 든 조각의 [번호, 한 변]찾기(c, r){ 왼쪽 = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 위쪽 = 0; w = a; // 남은 종이의 가로와 세로 h = b; 센수 = 0; // 지금까지 잘라 낸 조각의 수 間 (真) { もし (w >= h) { k = 数学.商(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 もし (c - 왼쪽 <= k * h) { 返す [센수 + 数学.商(c - 왼쪽 - 1, h) + 1, h]; } 센수 = 센수 + k; 왼쪽 = 왼쪽 + k * h; w = w - k * h; } でなければ { k = 数学.商(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 もし (r - 위쪽 <= k * w) { 返す [센수 + 数学.商(r - 위쪽 - 1, w) + 1, w]; } 센수 = 센수 + k; 위쪽 = 위쪽 + k * w; h = h - k * w; } }}繰り返す (i = 0; i < q; i++){ 줄 = コンソール.数読み(); 답 = 찾기(줄[0], 줄[1]); コンソール.書く(답[0] + " " + 답[1]);}