网易笔试题：饥饿的小易

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x_0。对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 * x + 3或者8 * x + 7。因为使用神秘力量要耗费太多体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置(比如：位置0，位置1,000,000,007，位置2,000,000,014等)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。 

输入描述:

输入一个初始位置x_0,范围在1到1,000,000,006

输出描述:

输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-1

输入例子:

125000000

输出例子:

1 核心思想：公式：(a*x+b)%c = (a*(x%c)+b)%c

C++代码

#include <iostream> #include <queue> #include <map> using namespace std; int findShell(long int x_0) { if(1 <= x_0 && x_0 <= 1000000006ll) { const long int a = 1000000007ll; x_0 %= a; queue<long int> q;// 并不保存 x， 而保存 x 的模值 map<long int, int> m;// <x的模值，移动次数> // 因为每次有两种移动法，看成一个二叉树，然后广度优先搜索之 q.push(x_0); m[x_0] = 0; while(!q.empty()) { long int current = q.front(); q.pop(); if(0 == current) return m[current]; if(m[current] <= 100000) { long int x1 = (4 * current + 3) % a;// x 的模值 if(m.end() == m.find(x1)) { m[x1] = m[current] + 1; q.push(x1); } long int x2 = (8 * current + 7) % a;// x 的模值 if(m.end() == m.find(x2)) { m[x2] = m[current] + 1; q.push(x2); } } } } return -1; } int main() { long int x_0; while(cin >> x_0) { cout << findShell(x_0) << endl; } return 0; }