第一行给出 a、b、q，用一个空格隔开。 接下来 q 行每行给出 c 和 r，用一个空格隔开。 1 ≤ a, b ≤ 10^15，1 ≤ q ≤ 5,000，1 ≤ c ≤ a，1 ≤ r ≤ b（都是整数，只给出数字，不带逗号）
输出
第一行是小块的个数和最小的小块的边长。 接着每个询问一行，是小块的编号和该小块的边长
样例 1 · stdin
10 7 6
1 1
7 7
8 1
10 6
9 7
10 7
stdout
6 1
1 7
1 7
2 3
3 3
5 1
6 1
样例 2 · stdin
1000000000000000 1 2
1 1
1000000000000000 1
stdout
1000000000000000 1
1 1
1000000000000000 1
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
这种剪法就是把欧几里得算法画成了图。 宽 w 不小于高 h 时，会得到“w 除以 h 的商”个边长为 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]);}