自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:14:41，当前版本为作者最后更新于2025-03-07 15:10:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

如果去模拟密码锁的拨动，那么完成这道题会很困难。不妨换个思路：枚举 $i$ 从 $0\sim 99999$，判断每个数是否是质数，若是则再计算需要拨动多少次才能拨动到拨盘的初始数字。

首先是判断质数部分。判断质数需要注意 $0,1$ 不是质数。此外，试除的时候应当枚举到 $x$ 的平方根。参考代码：

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}

较为麻烦的部分是计算需要拨动多少次。首先考虑将枚举的 $i$ 补全转化为 $5$ 位字符串，方便我们逐位判断。

string to5D(int x) { // 转换为 5 位字符串
    string ans = to_string(x);
    while (ans.size() < 5) ans = "0" + ans;
    return ans;
}

int totD(string x) { // 计算总拨动次数
    int ans = 0;
    for (int i = 0; i < 5; i++) {
        int xi = x[i] - '0'; // 当前字符串的数字
        int si = s[i] - '0'; // 初始字符串的数字
        ans += digD(xi, si); // 计算要拨动多少次
    }
    return ans;
}

接下来考虑完成 digD 这个函数。拨动有两种方案，要从其中取最小值。例如说从 $1$ 拨到 $4$，有两种方案。一种是 $1\to 2 \to 3 \to 4$，另外一种是 $1\to 0 \to 9 \to 8 \to \dots \to 4$。第一种方法需要的拨动次数是 $4-1=3$，第二种方法需要的拨动次数是 $10+1-4=7$，也即，$10$ 减去两个数字的差的绝对值。在两种方法中取最小值作为答案即可。

int digD(int x, int y) { 
    int diff = abs(x - y);
    return min(diff, 10 - diff);
}

最后，将上面的代码装填入主函数的枚举过程中，根据计算的结果更新答案即可。

for (int i = 2; i < 100000; i++) {
    if (isPrime(i)) {
        string num = to5D(i);
        int dist = totD(num);
        if (dist <= minT) {
            minT = dist;
            bestP = i;
        }
    }
}