上にも下にも果てしなく続く建物に、ボタンが二つだけのエレベーターがある。
▲ を一回押すとちょうど a 階上がり、▼ を一回押すとちょうど b 階下がる。
エレベーターは 0 階から出発し、t 階で止まりたい（t が負なら地下）。
▲ を x 回、▼ を y 回押すと着く階は x×a − y×b で、押す順番は関係ない。
x×a − y×b = t を満たす 0 以上の整数 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 ずつしか変わりません。
y ≥ 0（つまり x×a ≥ t）になるまで x を b/g ずつ上げれば、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）で % は負の結果を残します。
特に x を low の上に上げる low + (x - low) % step で余りが負だと、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 が負になることがあります。
y ≥ 0 になるまで x を b/g ずつ上げます。
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);