题意分析

• 空间站编号：共有$n$个空间站，编号为$0$到$n-1$。
• 飞船操作：飞船有两个按钮，分别标记数字$a$和$b$。
  • 按下$a$按钮：从当前站$s$移动到$(s + a) \mod n$。
  • 按下$b$按钮：从当前站$s$移动到$(s + b) \mod n$。
• 任务目标：从起始站$s$到目标站$t$，最少操作次数（即$x + y$最小，其中$x$是$a$按钮次数，$y$是$b$按钮次数）。
• 特殊要求：
  • 每次操作后需补充燃料，耗时$1$单位时间（即每次按钮操作均消耗$1$单位时间）。
  • 船长是左撇子，因此优先使用$a$按钮（即在$x + y$相同的情况下，选择$x$最大的解）。

解题思路

1. 问题建模

• 将空间站视为图节点，每次按钮操作视为有向边，边权为$1$（因为每次操作耗时$1$单位时间）。
• 问题转化为：在图中从$s$到$t$的最短路径（最少操作次数）。

2. 数学转化

• 设按$a$按钮$x$次，按$b$按钮$y$次，则目标方程为：
  [ (s + a \cdot x + b \cdot y) \mod n = t ] 等价于：
  [ a \cdot x + b \cdot y \equiv (t - s) \pmod{n} ]
• 这是一个线性同余方程，可通过扩展欧几里得算法求解。

3. 扩展欧几里得算法

• 设$d = \gcd(a, b, n)$，方程有解的条件是：
  [ (t - s) \mod d = 0 ] 否则无解（输出“no solution”）。
• 若有解，可求出方程的通解形式：
  [ x = x_0 + k \cdot \frac{b}{d}, \quad y = y_0 - k \cdot \frac{a}{d} ] 其中$(x_0, y_0)$是特解，$k$为整数。

4. 寻找最优解

• 目标1：最小化$x + y$。
  • 通过调整$k$，找到使$x + y$最小的非负整数解。
• 目标2：在$x + y$相同的情况下，最大化$x$（优先用$a$按钮）。
  • 选择$k$使得$x$尽可能大，同时保证$y \geq 0$。

5. 边界处理

• 由于$n$可能极大（$n < 2^{31}$），需避免暴力枚举，完全依赖数学方法求解。
• 需处理$n=1$、$a=0$或$b=0$等特殊情况。

6. 算法选择

• 使用扩展欧几里得算法求解方程，再通过数学推导筛选最优解。
• 时间复杂度：$O(\log(\min(a, b, n)))$，可高效处理大$n$。

标程

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;

LL n, a, b, c, s, t;

// 扩展欧几里得算法
LL extgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1; 
        y = 0;
        return a;
    }
    LL res = extgcd(b, a % b, x, y);
    LL tmp = x;
    x = y; 
    y = tmp - a / b * y;
    return res;
}

void solve(LL a, LL b, LL s, LL t, LL n) {
    bool swp = 0;
    if (a < b) {
        // 交换 a 和 b
        LL temp = a;
        a = b;
        b = temp;
        swp = true;
    }

    LL x1, y1, x2, y2;
    LL d = t - s;
    LL gcd1 = extgcd(a, b, x1, y1);
    LL gcd2 = extgcd(n, gcd1, x2, y2);

    if (-d % gcd2) {
        puts("no solution");
        return;
    }

    a /= gcd1; 
    b /= gcd1;
    n /= gcd2; 
    gcd1 /= gcd2; 
    d /= gcd2;

    x2 *= d; 
    y2 *= d;

    LL hmr = x2 / gcd1;
    y2 += n * hmr;

    LL ansx = 0, ansy = 0;
    LL minsum = 1LL << 62, x = x1 * y2, y = y1 * y2;
    LL sum, dx = x1 * n, dy = y1 * n;

    hmr = y / a;
    x += b * hmr; 
    y -= a * hmr;

    hmr = dy / a;
    dx += b * hmr; 
    dy -= a * hmr;

    while (1) {
        if (y < 0) {
            x -= b; 
            y += a;
        }
        else if (y >= a) {
            x += b; 
            y -= a;
        }
        sum = x + y;
        if (x >= 0 && (sum < minsum)) {
            ansx = x;
            ansy = y;
            minsum = sum;
        }
        if (x >= minsum) break;
        x += dx; 
        y += dy;
    }

    if (swp) swap(ansx, ansy);
    cout << ansx << " " << ansy << endl;
}

int main() {
    while (1) {
        cin >> n;
        if (n == 0) break;
        cin >> a >> b >> s >> t;
        solve(a, b, s, t, n);
    }
    return 0;
}