一栋向上向下都无限延伸的楼里，有一部只有两个按钮的电梯。
按一次 ▲ 恰好上升 a 层，按一次 ▼ 恰好下降 b 层。
电梯从 0 层出发，想停在 t 层（t 为负数表示地下）。
按 ▲ x 次、▼ y 次后到达 x×a − y×b 层，按的顺序无关。
在满足 x×a − y×b = t 的非负整数 x, y 中，找出 x + y 最小的一组，输出 "x y"。
如果不存在这样的 x, y，输出 -1。
使 x + y 最小的 (x, y) 总是唯一的。
依次回答 q 个询问，每个一行。
3 5 3 7 4 6 3 2 2 0
2 1 -1 0 0
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
x×a − y×b = t 只有在 g = gcd(a, b) 整除 t 时才有解。
扩展欧几里得算法还会给出满足 a×s + b×r = g 的 s，于是 x 从 s×(t/g) 除以 b/g 的余数开始，并且只能以 b/g 为步长变化。
把 x 按 b/g 往上加，直到 y ≥ 0（即 x×a ≥ t），x 和 y 就同时最小。
扩展欧几里得要返回三个值（g, s, r），各语言的写法不同：Python 返回元组 return g, y, x - (a // b) * y，JavaScript 返回数组 [g, x, y] 并解构，TypeScript 用元组类型 [number, number, number]，Java 用 record Ext(long g, long x, long y)，C# 用命名元组 (long g, long x, long y)，C++ 用 std::tuple 和 auto [g, x, y]，C 只能返回一个值，所以通过指针 long long *x, long long *y 填写。
Craykon 返回列表 [g, x, y]，用 r[0] 取出。
陷阱 ① 余数：s、t 和 x − low 可能为负，除 Python 外的所有语言（JavaScript、TypeScript、Java、C#、C、C++、Craykon）的 % 都会留下负数。
尤其是用 low + (x - low) % step 把 x 提到 low 以上时，余数为负会让 x 小于 low、y 变成负数 — 用 ((v % m) + m) % m 或 Java 的 Math.floorMod。
② 溢出：缩小后的 s 与缩小后的 t/g 相乘可达 10¹²，超过 Java、C#、C、C++ 的 int（约 21 亿）— 用 long/long long。
JavaScript 和 Craykon 的数在 2⁵³ 以内是精确的，这个范围没问题。
③ 直接用最小的 x 可能让 y 为负。
要把 x 按 b/g 往上加，直到 y ≥ 0。
import sys def ext_gcd(a, b): """a*x + b*y == g 인 (g, x, y)를 한꺼번에 돌려준다.""" if b == 0: return a, 1, 0 g, x, y = ext_gcd(b, a % b) return g, y, x - (a // b) * y def presses(a, b, t): """올라가기 횟수 x, 내려가기 횟수 y (x*a - y*b == t, x+y가 가장 작게). 안 되면 None.""" g, s, _ = ext_gcd(a, b) if t % g != 0: return None step = b // g # x는 이 간격으로만 바꿀 수 있다 x = (s % step) * ((t // g) % step) % step low = max(0, -(-t // a)) # y >= 0 이려면 x*a >= t x = low + (x - low) % step # low 이상에서 x와 나머지가 같은 가장 작은 수 return x, (x * a - t) // b def main(): data = sys.stdin.read().split() q = int(data[0]) out = [] for i in range(q): a, b, t = map(int, data[1 + 3 * i: 4 + 3 * i]) r = presses(a, b, t) out.append("-1" if r is None else f"{r[0]} {r[1]}") print("\n".join(out)) main()const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // a*x + b*y == g 인 [g, x, y]를 배열 하나로 돌려준다function extGcd(a, b) { if (b === 0) return [a, 1, 0]; const [g, x, y] = extGcd(b, a % b); return [g, y, x - Math.floor(a / b) * y];} // 수학의 나머지(늘 0 이상). JS의 %는 음수에서 음수가 나온다const mod = (v, m) => ((v % m) + m) % m; // [올라가기 횟수, 내려가기 횟수], 안 되면 nullfunction presses(a, b, t) { const [g, s] = extGcd(a, b); if (t % g !== 0) return null; const step = b / g; let x = (mod(s, step) * mod(t / g, step)) % step; const low = Math.max(0, Math.ceil(t / a)); // y >= 0 이려면 x*a >= t x = low + mod(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수 return [x, (x * a - t) / b];} const q = data[0];const out = [];for (let i = 0; i < q; i++) { const [a, b, t] = data.slice(1 + 3 * i, 4 + 3 * i); const r = presses(a, b, t); out.push(r === null ? "-1" : `${r[0]} ${r[1]}`);}console.log(out.join("\n"));import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // a*x + b*y == g 인 [g, x, y]를 튜플 하나로 돌려준다function extGcd(a: number, b: number): [number, number, number] { if (b === 0) return [a, 1, 0]; const [g, x, y] = extGcd(b, a % b); return [g, y, x - Math.floor(a / b) * y];} // 수학의 나머지(늘 0 이상). %는 음수에서 음수가 나온다const mod = (v: number, m: number): number => ((v % m) + m) % m; // [올라가기 횟수, 내려가기 횟수], 안 되면 nullfunction presses(a: number, b: number, t: number): [number, number] | null { const [g, s] = extGcd(a, b); if (t % g !== 0) return null; const step = b / g; let x = (mod(s, step) * mod(t / g, step)) % step; const low = Math.max(0, Math.ceil(t / a)); // y >= 0 이려면 x*a >= t x = low + mod(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수 return [x, (x * a - t) / b];} const q = data[0];const out: string[] = [];for (let i = 0; i < q; i++) { const [a, b, t] = data.slice(1 + 3 * i, 4 + 3 * i); const r = presses(a, b, t); out.push(r === null ? "-1" : `${r[0]} ${r[1]}`);}console.log(out.join("\n"));import java.io.*;import java.util.*; public class Main { // a*x + b*y == g 인 (g, x, y). Java 메서드는 값 하나만 돌려주니 record로 묶는다 record Ext(long g, long x, long y) {} static Ext extGcd(long a, long b) { if (b == 0) return new Ext(a, 1, 0); Ext e = extGcd(b, a % b); return new Ext(e.g(), e.y(), e.x() - (a / b) * e.y()); } // 수학의 나머지(늘 0 이상). Java의 %는 음수에서 음수가 나온다 static long mod(long v, long m) { return Math.floorMod(v, m); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); long t = Long.parseLong(st.nextToken()); Ext e = extGcd(a, b); if (t % e.g() != 0) { out.append("-1\n"); continue; } long step = b / e.g(); long x = mod(e.x(), step) * mod(t / e.g(), step) % step; long low = Math.max(0, Math.floorDiv(t + a - 1, a)); // y >= 0 이려면 x*a >= t x = low + mod(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수 out.append(x).append(' ').append((x * a - t) / b).append('\n'); } System.out.print(out); }}using System;using System.Text; class Program{ // a*x + b*y == g 인 (g, x, y)를 튜플로 한꺼번에 돌려준다 static (long g, long x, long y) ExtGcd(long a, long b) { if (b == 0) return (a, 1, 0); var (g, x, y) = ExtGcd(b, a % b); return (g, y, x - (a / b) * y); } // 수학의 나머지(늘 0 이상). C#의 %는 음수에서 음수가 나온다 static long Mod(long v, long m) => ((v % m) + m) % m; static void Main() { int q = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int i = 0; i < q; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long a = long.Parse(p[0]), b = long.Parse(p[1]), t = long.Parse(p[2]); var (g, s, _) = ExtGcd(a, b); if (t % g != 0) { out_.Append("-1\n"); continue; } long step = b / g; long x = Mod(s, step) * Mod(t / g, step) % step; long low = t > 0 ? (t + a - 1) / a : 0; // y >= 0 이려면 x*a >= t x = low + Mod(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수 out_.Append(x).Append(' ').Append((x * a - t) / b).Append('\n'); } Console.Write(out_); }}#include <iostream>#include <tuple> // a*x + b*y == g 인 (g, x, y)를 tuple로 한꺼번에 돌려준다std::tuple<long long, long long, long long> extGcd(long long a, long long b) { if (b == 0) return {a, 1, 0}; auto [g, x, y] = extGcd(b, a % b); return {g, y, x - (a / b) * y};} // 수학의 나머지(늘 0 이상). C++의 %는 음수에서 음수가 나온다long long mod(long long v, long long m) { return (v % m + m) % m; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; std::cin >> q; while (q--) { long long a, b, t; std::cin >> a >> b >> t; auto [g, s, r] = extGcd(a, b); (void)r; if (t % g != 0) { std::cout << "-1\n"; continue; } long long step = b / g; long long x = mod(s, step) * mod(t / g, step) % step; long long low = t > 0 ? (t + a - 1) / a : 0; // y >= 0 이려면 x*a >= t x = low + mod(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수 std::cout << x << ' ' << (x * a - t) / b << '\n'; }}#include <stdio.h> /* a*x + b*y == g. C 함수는 값 하나만 돌려주니 x, y는 포인터로 받아 채운다 */long long ext_gcd(long long a, long long b, long long *x, long long *y) { if (b == 0) { *x = 1; *y = 0; return a; } long long x1, y1; long long g = ext_gcd(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return g;} /* 수학의 나머지(늘 0 이상). C의 %는 음수에서 음수가 나온다 */long long mod(long long v, long long m) { return (v % m + m) % m;} int main(void) { int q; scanf("%d", &q); while (q--) { long long a, b, t, s, r; scanf("%lld %lld %lld", &a, &b, &t); long long g = ext_gcd(a, b, &s, &r); if (t % g != 0) { puts("-1"); continue; } long long step = b / g; long long x = mod(s, step) * mod(t / g, step) % step; long long low = t > 0 ? (t + a - 1) / a : 0; /* y >= 0 이려면 x*a >= t */ x = low + mod(x - low, step); /* low 이상에서 x와 나머지가 같은 가장 작은 수 */ printf("%lld %lld\n", x, (x * a - t) / b); } return 0;}// a*x + b*y == g 인 [g, x, y]를 목록 하나로 돌려준다확장유클리드(a, b){ 如果 (b == 0) { 返回 [a, 1, 0]; } r = 확장유클리드(b, a % b); 返回 [r[0], r[2], r[1] - 数学.商(a, b) * r[2]];} // 수학의 나머지(늘 0 이상). %는 음수에서 음수가 나온다나머지(v, m){ 返回 (v % m + m) % m;} q = 控制台.读行().转数字();out = "";循环 (i = 0; i < q; i++){ abt = 控制台.读数字(); a = abt[0]; b = abt[1]; t = abt[2]; e = 확장유클리드(a, b); g = e[0]; 如果 (t % g != 0) { out += "-1\n"; } 否则 { step = 数学.商(b, g); x = 나머지(e[1], step) * 나머지(数学.商(t, g), step) % step; low = 数学.较大值(0, 数学.向上取整(t / a)); // y >= 0 이려면 x*a >= t x = low + 나머지(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수 out += x + " " + 数学.商(x * a - t, b) + "\n"; }}控制台.接着输出(out);