An elevator with two buttons

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){    if (b == 0)    {        return [a, 1, 0];    }    r = 확장유클리드(b, a % b);    return [r[0], r[2], r[1] - Mathf.Quot(a, b) * r[2]];} // 수학의 나머지(늘 0 이상). %는 음수에서 음수가 나온다나머지(v, m){    return (v % m + m) % m;} q = Console.ReadLine().ToNumber();out = "";for (i = 0; i < q; i++){    abt = Console.ReadNumbers();    a = abt[0];    b = abt[1];    t = abt[2];    e = 확장유클리드(a, b);    g = e[0];    if (t % g != 0)    {        out += "-1\n";    }    else    {        step = Mathf.Quot(b, g);        x = 나머지(e[1], step) * 나머지(Mathf.Quot(t, g), step) % step;        low = Mathf.Max(0, Mathf.Ceil(t / a)); // y >= 0 이려면 x*a >= t        x = low + 나머지(x - low, step); // low 이상에서 x와 나머지가 같은 가장 작은 수        out += x + " " + Mathf.Quot(x * a - t, b) + "\n";    }}Console.Write(out);