题解 | 饥饿的小易

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int solve(int x0) {
        const int MOD = 1000000007;
        const int MAX_STEPS = 100000;
        
        // 如果初始位置就能被MOD整除，直接返回0
        if (x0 % MOD == 0) return 0;
        
        // 使用集合记录已访问的位置
        unordered_set<int> visited;
        // 队列存储<位置, 步数>
        queue<pair<int, int>> q;
        
        q.push({x0, 0});
        visited.insert(x0);
        
        while (!q.empty()) {
            int pos = q.front().first;
            int steps = q.front().second;
            q.pop();
            
            if (steps >= MAX_STEPS) continue;
            
            // 尝试两种移动方式
            long long next1 = (4LL * pos + 3) % MOD;
            long long next2 = (8LL * pos + 7) % MOD;
            
            // 检查第一种移动方式
            if (next1 == 0) return steps + 1;
            if (visited.find(next1) == visited.end()) {
                visited.insert(next1);
                q.push({next1, steps + 1});
            }
            
            // 检查第二种移动方式
            if (next2 == 0) return steps + 1;
            if (visited.find(next2) == visited.end()) {
                visited.insert(next2);
                q.push({next2, steps + 1});
            }
        }
        
        return -1;
    }
};

int main() {
    int x0;
    cin >> x0;
    Solution solution;
    cout << solution.solve(x0) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int solve(int x0) {
        final int MOD = 1000000007;
        final int MAX_STEPS = 100000;
        
        // 如果初始位置就能被MOD整除，直接返回0
        if (x0 % MOD == 0) return 0;
        
        // 使用集合记录已访问的位置
        Set<Integer> visited = new HashSet<>();
        // 队列存储<位置, 步数>
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[]{x0, 0});
        visited.add(x0);
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int pos = current[0];
            int steps = current[1];
            
            if (steps >= MAX_STEPS) continue;
            
            // 尝试两种移动方式
            long next1 = (4L * pos + 3) % MOD;
            long next2 = (8L * pos + 7) % MOD;
            
            // 检查第一种移动方式
            if (next1 == 0) return steps + 1;
            if (!visited.contains((int)next1)) {
                visited.add((int)next1);
                queue.offer(new int[]{(int)next1, steps + 1});
            }
            
            // 检查第二种移动方式
            if (next2 == 0) return steps + 1;
            if (!visited.contains((int)next2)) {
                visited.add((int)next2);
                queue.offer(new int[]{(int)next2, steps + 1});
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x0 = sc.nextInt();
        System.out.println(solve(x0));
        sc.close();
    }
}

def solve(x0: int) -> int:
    MOD = 1000000007
    MAX_STEPS = 100000
    
    # 如果初始位置就能被MOD整除，直接返回0
    if x0 % MOD == 0:
        return 0
    
    # 使用集合记录已访问的位置，避免重复访问
    visited = set()
    # 队列存储(位置, 步数)
    queue = [(x0, 0)]
    visited.add(x0)
    
    while queue:
        pos, steps = queue.pop(0)
        
        if steps >= MAX_STEPS:
            continue
            
        # 尝试两种移动方式
        next_positions = [
            (4 * pos + 3) % MOD,  # 第一种移动方式
            (8 * pos + 7) % MOD   # 第二种移动方式
        ]
        
        for next_pos in next_positions:
            # 如果找到能被MOD整除的位置
            if next_pos == 0:
                return steps + 1
                
            # 如果是新位置，加入队列
            if next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, steps + 1))
    
    return -1

# 读取输入
x0 = int(input())
# 输出结果
print(solve(x0))