B3730 [信息与未来 2017] 密码锁

chen_zhe · 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;
        }
    }
}