饥饿的小易 小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。

题目描述

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置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

示例1

输入

125000000

输出

1

记f(x)=4*x+3，g(x)=8*x+7，h(t, x)=((x+1)<

4*x+3即为4*(x+1)-1即为((x+1)<<2)-1即为h(2, x)

8*x+7即为8*(x+1)-1即为((x+1)<<3)-1即为h(3, x)

因此有h(2, x)=f(x)，h(3, x)=g(x)

16*x+15即为16*(x+1)-1即为((x+1)<<4)-1即为h(4, x)即为

(( (((x+1)<<2)-1) +1)<<2)-1即为f(f(x))即为h(2, h(2, x))

32*x+31即为32*(x+1)-1即为((x+1)<<5)-1即为h(5, x)即为

(( (((x+1)<<3)-1) +1)<<2)-1或(( (((x+1)<<2)-1) +1)<<3)-1

即为f(g(x))或g(f(x))即为h(2, h(3, x))或h(3, h(2, x))

依次类推，发现

需要的次数    生成的结果
1             (x+1)<<2-1
1             (x+1)<<3-1
2             (x+1)<<4-1
2             (x+1)<<5-1
2             (x+1)<<6-1
3             (x+1)<<7-1
3             (x+1)<<8-1
3             (x+1)<<9-1
4             (x+1)<<10-1
4             (x+1)<<11-1
4             (x+1)<<12-1
5             (x+1)<<13-1
每三个一组，由初等数论基础知识可得每次都可以mod上操作数再进行移位操作不影响结果的正确性，因此有代码如下：

#include using namespace std;
typedef unsigned long long ull;int main() {const ull mod = 1000000007;const ull cntMax = 100000;ull x = 0;cin >> x;ull t;t = ((x + 1) << 2) - 1;if (t % mod == 0) {cout << 1;return 0;}t = ((x + 1) << 3) - 1;if (t % mod == 0) {cout << 1;return 0;}ull x4 = ((x + 1) << 4) % mod;ull x5 = ((x + 1) << 5) % mod;ull x6 = ((x + 1) << 6) % mod;for (ull cnt = 2; cnt <= cntMax; cnt++) {if ((x4 - 1) % mod == 0) {cout << cnt;return 0;}if ((x5 - 1) % mod == 0) {cout << cnt;return 0;}if ((x6 - 1) % mod == 0) {cout << cnt;return 0;}x4 = (x4 << 3) % mod;x5 = (x5 << 3) % mod;x6 = (x6 << 3) % mod;}cout << -1;return 0;
}

运行结果：

运行时间：6ms

占用内存：484k

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！