解题思路

给定两种操作：把当前数乘以 x 或乘以 y。若能从 a 变到 b，设比例 r = b / a（必须满足 b % a == 0），那么一切操作的乘积等价于把 r 分解成

此时最少操作次数就是使用的总步数 i + j。因此问题转化为：判断 r 是否能表示为 x^i * y^j，并在可行时最小化 i + j。

做法上采用“幂枚举 + 试除”：

1. 若 b % a != 0，直接输出 -1。
2. 令 r = b / a。枚举 i = 0..⌊log_x r⌋，维护 powX = x^i（只要不超过 r）。
3. 若 r % powX == 0，设 q = r / powX，不断用 y 试除 q，统计能除多少次（得到 j）。若最终 q == 1，则当前 (i, j) 有效，更新答案 ans = min(ans, i + j)。
4. 若所有枚举都失败，则输出 -1。

该方法等价于在乘法半群 {x,y} 上找一组非负整数解并最小化 i+j，顺序无关（只看次数）。也可反向做一个在 r 上的 BFS（边为能整除时除以 x 或 y），由于 r ≤ 1e9，步数 ≤ 30，复杂度也可行；但“幂枚举 + 试除”实现更简单。

复杂度分析

• 时间复杂度：O(log_x r * log_y r)，因为 i 的取值约为 O(log_x r)，每次检查是否是 y 的幂需要 O(log_y r) 次试除。上界非常小（r ≤ 1e9 时不超过约 30*30）。
• 空间复杂度：O(1)，仅用到常数额外变量。

代码实现

Python

# 功能函数：返回最少操作次数；不可达则返回 -1
def min_steps(x: int, y: int, a: int, b: int) -> int:
    if b % a != 0:
        return -1
    r = b // a
    if r == 1:
        return 0

    ans = None
    pow_x = 1
    i = 0
    # 枚举 i，使得 pow_x = x^i，不超过 r
    while pow_x <= r:
        if r % pow_x == 0:
            q = r // pow_x
            cnt = 0
            # 试除 y，统计 j
            while q % y == 0:
                q //= y
                cnt += 1
            if q == 1:
                steps = i + cnt
                if ans is None or steps < ans:
                    ans = steps
        # 继续下一个 i
        # 防止溢出：仅在 pow_x <= r // x 时再乘
        if pow_x > r // x:
            break
        pow_x *= x
        i += 1

    return -1 if ans is None else ans

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().strip().split()
    x, y, a, b = map(int, data)
    print(min_steps(x, y, a, b))

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    // 外部函数：返回最少操作次数；不可达返回 -1
    static long minSteps(long x, long y, long a, long b) {
        if (b % a != 0) return -1;
        long r = b / a;
        if (r == 1) return 0;

        Long ans = null;
        long powX = 1L;
        int i = 0;
        while (powX <= r) {
            if (r % powX == 0) {
                long q = r / powX;
                int cnt = 0;
                // 试除 y，统计 j
                while (q % y == 0) {
                    q /= y;
                    cnt++;
                }
                if (q == 1) {
                    long steps = (long)i + cnt;
                    if (ans == null || steps < ans) ans = steps;
                }
            }
            // 防止乘法越界/超过 r
            if (powX > r / x) break;
            powX *= x;
            i++;
        }
        return ans == null ? -1 : ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().trim().split("\\s+");
        long x = Long.parseLong(parts[0]);
        long y = Long.parseLong(parts[1]);
        long a = Long.parseLong(parts[2]);
        long b = Long.parseLong(parts[3]);
        System.out.println(minSteps(x, y, a, b));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 外部函数：返回最少操作次数；不可达返回 -1
long long minSteps(long long x, long long y, long long a, long long b) {
    if (b % a != 0) return -1;
    long long r = b / a;
    if (r == 1) return 0;

    long long ans = -1;
    long long powX = 1; // x^i
    int i = 0;
    while (powX <= r) {
        if (r % powX == 0) {
            long long q = r / powX;
            int cnt = 0;
            // 试除 y，统计 j
            while (q % y == 0) {
                q /= y;
                cnt++;
            }
            if (q == 1) {
                long long steps = (long long)i + cnt;
                if (ans == -1 || steps < ans) ans = steps;
            }
        }
        // 防止乘法越界/超过 r
        if (powX > r / x) break;
        powX *= x;
        i++;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long x, y, a, b;
    if (!(cin >> x >> y >> a >> b)) return 0;
    cout << minSteps(x, y, a, b) << "\n";
    return 0;
}

题目内容

小红可以对一个数进行如下两种操作：将这个数乘以 $x$ 或将这个数乘以 $y$ 。操作的次数是没有限制的。

小红想知道，自己最少经过多少次操作以后，可以把 $a$ 变成 $b$ ?

输入描述

四个正整数 $x,y,a,b$，用空格隔开。

$2 ≤ x,y ≤ 100$

$1 ≤ a,b≤ 10^9$

输出描述

如果小红无论如何都无法把 $a$ 变成 $b$ ，则输出 $-1$ 。否则输出小红操作的最少次数。可以证明，如果存在某种操作，那么最少次数定是固定的。

样例1

输入

2 3 5 20

输出

2

说明

$x=2,y=3$，进行两次乘 $2$ 操作，可以把 $5$ 变成 $20$ 。