题目描述
小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置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
1 import java.util.Scanner; 2 3 /** 4 * 饥饿的小易 5 * 1、分析 6 * 4x+3 7 * 8x+7 8 * 4(4x+3)+3 = 16x+15 9 * 4(8x+7)+3 = 8(4x+3)+7 =32x+31 =32(x+1)-1 10 * 每次 变换 得到的数 都是 11 * 我们设 2^n 为 times,也有times(x+1)-1,a=2^n * x +(2^n)-112 * 循环检查 a%N 是否为0 判断 13 * 2、最多使用 100000 次魔法 最多情况下就是都使用 8x+7,14 * 而此时我们是使用2来循环 ,2^3 = 8 那么我们就需要循环 300000次 15 * 但是，无论是 int 还是 long 都无法表示那么大的数，所以我们需要做同余处理来进行替换16 * 17 * 同余：18 如果 a%m =b%m 那么我们就说 ab关于模m同余 ，记作 a≡b(mod m) 19 不难理解 b = a%m 有 a≡b(mod m) 20 那么： 21 设 a 、b 对于 m 的余数 都为 mod,可以这样表示： 22 a = c1*m + mod 23 b = c2*m + mod(a1、a2为不同的整数) 24 a(x+1)-1 = (c1*m + mod)*(x+1)-1 = c1*m*(x+1) + mod*(x+1)-1 25 b(x+1)-1 = (c2*m + mod)*(x+1)-1 = c2*m*(x+1) + mod*(x+1)-1 26 c1*m*(x+1)、 c2*m*(x+1) 都是可以被 m整除 27 所以 a(x+1)-1 b(x+1)-1 对于 m 的余数 都为(mod*(x+1)-1)%m 28 也就是说 a≡b(mod m) ,ab做相同的加减乘除变换之后,对于m同余仍然成立 29 30 因此我们可以使用 times=times%N 来求 times对于N的同余数 ，前后 (times*(x+1)-1)%N 值不变可以做替换31 * 32 * 33 * 34 * 4x+3 等于两次 2x+1 8x+7 等于 三次 2x+135 * 36 * @author Dell37 *38 */39 public class Main {40 static public long x = 125000000;41 static public long N = 1000000007;42 static public long count = -1;43 static public long times = 4; //第一次最小为444 static public void f() {45 for (int i = 1; i <=300000; i++) {46 long mod = (times*(x+1)-1)%N;47 if (mod == 0) {48 // 取值 尽可能多取8来减小步数， 所以除以349 // times从4 开始 就是 2^2 而 i 从1开始必须加150 count=(i+1)/3 + ((i+1)%3==0?0:1);51 return;52 }53 // 求下一个 times 并做替换54 times = (times*2)%N;55 }56 }57 public static void main(String[] args) {58 Scanner sc = new Scanner(System.in);59 x = sc.nextLong();60 f();61 System.out.println(count);62 }63 }