题目描述

给你两个整数 n 和 m，两个整数有 相同的 数位数目。

你可以执行以下操作 任意 次：

• 从 n 中选择 任意一个 不是 9 的数位，并将它 增加 1。
• 从 n 中选择 任意一个 不是 0 的数位，并将它 减少 1。

任意时刻，整数 n 都不能是一个 质数，意味着一开始以及每次操作以后 n 都不能是质数。

进行一系列操作的代价为 n 在变化过程中 所有 值之和。

请你返回将 n 变为 m 需要的 最小 代价，如果无法将 n 变为 m，请你返回 -1。

一个质数指的是一个大于 1 的自然数只有 2 个因子：1 和它自己。

样例

输入：n = 10, m = 12

输出：85

解释：

我们执行以下操作：

增加第一个数位，得到 n = 20。
增加第二个数位，得到 n = 21。
增加第二个数位，得到 n = 22。
减少第一个数位，得到 n = 12。

输入：n = 4, m = 8

输出：-1

解释：

无法将 n 变为 m。

输入：n = 6, m = 2

输出：-1

解释：

由于 2 已经是质数，我们无法将 n 变为 m。

限制

• 1 <= n, m < 10^4
• n 和 m 包含的数位数目相同。

算法

(线性筛，Dijkstra 最短路) $O(n \log n)$

1. 首先用线性筛找到所有的质数。
2. 从 $n$ 开始通过 Dijkstra 算法求解到 $m$ 的最短路径。
3. 枚举每一位数字并尝试转移松弛。

时间复杂度

• 线性筛的时间复杂度为 $O(n)$。
• 图共有 $O(n)$ 个节点，每个点的边数为常数。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储线性筛的结果，距离数组和堆。

C++ 代码

const int N = 10000;

int primes[N], cnt;
bool is_not_prime[N];

auto init = []{
    is_not_prime[1] = true;

    for (int i = 2; i < N; i++) {
        if (!is_not_prime[i])
            primes[cnt++] = i;

        for (int j = 0; j < cnt && i * primes[j] < N; j++) {
            is_not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }

    return 0;
}();

class Solution {
private:
    int d[N];

public:
    int minOperations(int n, int m) {
        if (!is_not_prime[n] || !is_not_prime[m])
            return -1;

        for (int i = 0; i < N; i++)
            d[i] = INT_MAX;

        priority_queue<pair<int, int>> heap;
        d[n] = n;
        heap.push(make_pair(0, n));

        while (!heap.empty()) {
            auto u = heap.top();
            heap.pop();

            if (u.second == m)
                break;

            if (d[u.second] < -u.first)
                continue;

            for (int p = 1; p < N; p *= 10) {
                if (u.second / p == 0)
                    break;

                int x = u.second / p % 10;
                int b = u.second - x * p;

                if (x > 0) {
                    int y = b + (x - 1) * p;
                    if (is_not_prime[y] && d[y] > d[u.second] + y) {
                        d[y] = d[u.second] + y;
                        heap.push(make_pair(-d[y], y));
                    }
                }

                if (x < 9) {
                    int y = b + (x + 1) * p;
                    if (is_not_prime[y] && d[y] > d[u.second] + y) {
                        d[y] = d[u.second] + y;
                        heap.push(make_pair(-d[y], y));
                    }
                }
            }
        }

        return d[m] == INT_MAX ? -1 : d[m];
    }
};