饥饿的小易

核心问题

1. 4x+3和8x+7的数学操作，可以用二进制的左移和补1表示

   y = 4*x+3,相当于x的二进制左移2位，然后空位补1，即原先x的二进制为#####,则y的二进制为#####11，

   y = 8*x+3,相当于y的二进制左移3位，然后空位补1，即原先x的二进制为#####,则y的二进制为#####111

2. 小易的移动，最终可以表达成4x+3操作进行了m次，8x+7操作进行了n次

   4*x+3操作进行m次，则x的二进制后面增加2m个1

   8*x+7操作进行n次，则x的二进制后面增加了3n个1

   小易的移动，最终可以表达为：x的二进制后面增加了（2m+3n）个1

   移动的顺序对其到达没有影响

3. 小易移动次数的分析

   初始位置为0，则直接满足，需移动0次

   初始位置不为0，则记times = （2m+3n）,m取1到10_0000,n取1到10_0000

   所以，times的取值范围为[2,30_0000]。即：最多30_0000次搜索，就能获得结果。

4. 由于幂次操作数值过大，需要作出变换。参考牛客网用户。

代码如下

import java.util.Scanner;

/**
 * Created by Halley on 2017/8/11.
 */
public class Main {
    public static final long LIMIT = 300000;//最多搜索次数
    public static final long N = 1000000007;//求余

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            System.out.println(sol(sc.nextLong()));
        }
    }

    //次数判定方法
    public static long sol(long in){
        //如果初始位置为0，则直接可行，返回0次
        if(in == 0){
            return 0L ;
        }else{//初始位置不为0，则开始搜索
            return search(in);
        }
    }

    //不为0时的搜索
    public static long search(long in){//参数：初始坐标
        long temp = in;
        //遍历，获取最小位移
        for(int i=1;i<=LIMIT;i++){
            //long temp = (in+1)*(long)Math.pow(2,i)-1;//当循环较大时，幂次太高，数字超出范围，报错
            //递推
            temp = (temp * 2 + 1 ) % N;
            if( temp % N == 0 ){
                //i是符合条件的最小偏移，然后对其进行分解
                for(int j =0;j<=(i / 2);j++){//j对应a值
                    if((i - 2*j) % 3 == 0){
                        return ((i+j)/3);
                    }
                }
            }
        }
        //超过最大次数还没匹配，则输出-1
        return -1L;
    }
}

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007LL
#define MAX 100000
int main(){
    unordered_map<long long,int> vist;
    for(long long x;cin>>x;vist.clear()){
        queue<long long> q;
        for(long long xx=vist[x]=1,q.push(x);q.size();){
            x = q.front();
            q.pop();
            if (x==0) break;
            if (vist[x]>MAX) continue;            
            xx=((x<<2)+3)%MOD;
            if (vist.find(xx)==vist.end()) {
                q.push(xx);
                vist[xx]=vist[x]+1;
            }
            xx=((x<<3)+7)%MOD;
            if (vist.find(xx)==vist.end()){
                q.push(xx);
                vist[xx]=vist[x]+1;
            }
        }
        cout<<(q.size()?vist[x]-1:-1)<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
#define MOD 1000000007LL
#define MAX 100000
#define ITERATOR 10000
int main(){
    unordered_map<long long,int> vist;
    for(long long i,n=1;1;++n,vist.clear()){
        i=rand()%MOD;   //伪随机数
        queue<long long> q;
        long long it=0,xx=1,x;
        for(vist[i]=1,q.push(i);q.size();++it){ //迭代次数
            x = q.front();
            q.pop();
            if (x==0) break;
            if (vist[x]>MAX) continue;           
            xx=((x<<2)+3)%MOD;
            if (vist.find(xx)==vist.end()) {
                q.push(xx);
                vist[xx]=vist[x]+1;
            }
            xx=((x<<3)+7)%MOD;
            if (vist.find(xx)==vist.end()){
                q.push(xx);
                vist[xx]=vist[x]+1;
            }
        }
        //cout<<(q.size()?vist[x]-1:-1)<<endl;
        if (it>ITERATOR) cout<<n<<" x="<<i<<", iterate="<<it<<endl;
    }
    return 0;
}

下面是我的部分运行结果，第一列是标号，第二列是输入的x，第三列是迭代次数。

最后奉劝大家，多思考是对的，但是思考一半就说别人的方法慢，迭代2^100000次，就很low了。

#include<stdio.h>
#include<map>
#include<queue>
using namespace std;
const long long mod=1000000007;
struct node{
    long long x,step;
    node(long long x,long long step):x(x),step(step){}
};
int main(){
    long long x;
    while(scanf("%lld",&x)!=EOF){
        queue<node> Q;
        map<long long,int> book;
        Q.push(node(x,0)),book[x]=1;
        long long res=-1;
        while(!Q.empty()){
            node head=Q.front();Q.pop();
            if(head.x%mod==0){
                res=head.step;
                break;
            }
            if(head.step>100000) break;
            long long x1=(4*head.x+3)%mod,x2=(8*head.x+7)%mod;
            if(book.count(x1)==0){
                book[x1]=1;
                Q.push(node(x1,head.step+1));
            }
            if(book.count(x2)==0){
                book[x2]=1;
                Q.push(node(x2,head.step+1));
            }
        }
        printf("%lld\n",res);
    }
}//直接bfs就可以啦~

原理也是这个

1. 4x+3=4(x+1)-1
2. 8x+7=8(x+1)-1

式子1套式子1
4(4x+3)+3=16(x+1)-1
(x+1)前的数字是这种规律
4,8,16,32....
转换下 2^2,2^3,2^4....

现在我可以列出所有的公式
4(x+1)-1
8(x+1)-1
16(x+1)-1
...

假设32(x+1)-1这个公式中了,其实也就是2^4*(x+1)-1中了。

可以发现使用此时是N除3并向上取整

import sys
x0=int(sys.stdin.readline().strip())
count=0
s=[]
key=-1
fac=2
for i in range(1,3*100000):
    if (fac*(x0+1)-1)%1000000007==0:
        key=i
        break
    #防止fac过大，所以要取模下
    fac=fac*2%1000000007
if key==-1:
    print(-1)
else:
    print((key-1)//3+1)

x = int(input())
a = 2 # next number is 2**a(x+1)-1
if x % 1000000007 == 0:
    print(0)
else:
    x = (4*x +3) % 1000000007
    while x and a < 300001:
        x = (x*2 +1)% 1000000007
        a += 1
    if x:
        print(-1)
    else:
        print((a+2)//3)

	

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);		
		
		while(in.hasNext()){
			int x=in.nextInt();
			Map<Long, Integer> map=new HashMap<Long, Integer>();
			
			Queue<Long> queue=new LinkedList<Long>();
			queue.offer((long)x);
			map.put((long)x, 1);

			while(!queue.isEmpty()){
				long n=queue.poll();
				if(n==0) {System.out.println(map.get(n)-1); return;}
				if(map.get(n)>=100001) continue;
				
				if(!map.containsKey((4*n+3)%1000000007)){
					map.put((4*n+3)%1000000007, map.get(n)+1);
					queue.offer((4*n+3)%1000000007);
				}
				if(!map.containsKey((8*n+7)%1000000007)){
					map.put((8*n+7)%1000000007, map.get(n)+1);
					queue.offer((8*n+7)%1000000007);
				}
			}
			System.out.println(-1);
		}
	}
}

	

一个简单的方法

#include 
using namespace std;
int main(){
    long long x0;
    long long res=-1;
    long long a=1000000007;
    cin>>x0;
    if(x0%a==0)
        return 0;
    x0=(x0*4+3)%a;
    int i=3;
    while(i<=300000){
        x0=(x0*2+1)%a;
        if(x0==0){
            if(i%3==0)
                res=i/3;
            else
                res=i/3+1;
            break;
        }
        i++;
    }
    cout<<res<<endl;
    return 0;
}

#include<iostream>
using namespace std;
int main()
{
    int rst = -1;
    long long x0 = 0, n1 = 1, n2 = 1, n0 = 0;
    cin >> x0;
    n0 = x0 + 1;
    n1 = (x0 + 1)*4;
    n2 = (x0 + 1)*16;
    for(int k = 0; k<=100000;k++)
    {
        if((n0 - 1)%1000000007 == 0)
        {
            rst = k;
            break;
        }
        if((n1 - 1)%1000000007 == 0 && k <= 99999)
        {
            rst = k + 1;
            break;
        }
        if((n2 - 1)%1000000007 == 0 && k<= 99998)
        {
            rst = k + 2;
            break;
        }
        n0 %= 1000000007;
        n1 %= 1000000007;
        n2 %= 1000000007;
        n0 *= 8;
        n1 *= 8;
        n2 *= 8;
    }
    cout << rst;
    return 0;
}

找规律，迭代时间复杂度太高

#include<stdio.h>

/** 受各位大神指点，用数学公式做**/ 
int main()
{
    int i=0;
    long long zs=2, x=0, temp=0;
    scanf( "%lld", &x);

    for( i=2; i<100000*3; i++)
    {
        zs=(zs*2)%1000000007;
        temp=(zs*(x+1)-1)%1000000007;

        if( temp==0)
        {
            if( i%3==0) printf("%d", i/3);
            else printf("%d", i/3+1);
            break;
        }
    }
    if( i==100000*3) printf( "-1");

    return 0;
}

#include <iostream>
using namespace std;
const long long STEP = 1000000007;
int main(void)
{
    bool flag(1); //这个是为了在循环中强制跳出
    long long x, dist, cont;
    cin >> x;
    for (int i = 0; i < 3 && flag == 1; i++) //所有f(x)可能性
    {
        dist = x;       //没找到重置初始位置信息
        cont = 0;       //没找到就要重置计数
        for (int j = 0; j < i; j++) //先进行f(x)求解，对应0 1 2次
        {
            dist = (4 * dist + 3) % STEP; //结果就是下次的步进数，想不明白可以画个图
            cont++;
            if (dist == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
        {
            while (cont <= 100000 && flag == 1) //设置最大次数
            {
                dist = (8 * dist + 7) % STEP; //与f(x)求解方法一样
                cont++;
                if (dist == 0)
                {
                    flag = 0;
                    break;
                }
            }
        }
    }
    if (cont <= 100000)
        cout << cont << endl;
    else
        cout << -1 << endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int mod = (int) (1e9+7);
        int count = -1;
        int time = 4;
        for(int i = 1;i <= 300000;i++){
            long x = (time * (long)(n) + time -1) % mod; //注意long所在的位置，很关键
            //long x=((long )(n)*time+time-1)%mod;
            if(x == 0){
                count = (i+1)/3 + ((i+1)%3 != 0 ? 1:0);
                /*if((i+1) %3 != 0){
                    count = (i+1)/3 + 1;
                }
                else {
                    count = (i+1)/3;
                }*/
                break;
            }
            time = (time*2) % mod;
        }
    
            System.out.println(count);
    }
}

x = int(input())
res, m = 100001, 1000000007
if x%m==0: res = 0
else:
    ai = (2*(x+1)-1)%m
    for i in range(2, 300001):
        ai = (2*ai+1)%m
        if ai==0:
            res = i//3+(i%3!=0)
            break
print(res if res<=100000 else -1)

import java.util.Scanner;

public class Main {
	
	static int mod = 1000000007;
	static int LIMIT = 100000;
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		long x = in.nextLong();
		int cnt = 0;
		for(int i=0; i<LIMIT; i++){
			x %= mod;
			if(x == 0){
				System.out.println(cnt);
				return;
			}else{
				if(g(g(x)) > mod){
					long tmp = x;
					for(int j=1; j<=2; j++){
						tmp = f(tmp);
						if(tmp % mod == 0){
							System.out.println(cnt+j);
							return;
						}
					}
				}
                x = g(x);
				cnt++;
			}
		}
		System.out.println("-1");
	}
	
	private static Long f(long x){
		return 4*x+3;
	}
	
	private static Long g(long x){
		return 8*x+7;
	}

}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
const long long Mod=1000000007;
struct node
{
    long long x;
    int sum;
};
map<long long,int>Map;
void bfs(long long sx)
{
    queue<node>Q;
    node Node;
    Node.x=sx;Node.sum=0;
    Q.push(Node);
    while(!Q.empty())
    {
        if(Map[0]!=0) return;
        node tmp=Q.front();
        Q.pop();
        node newNode;
        newNode.x=(4*tmp.x+3)%Mod;
        newNode.sum=tmp.sum+1;
        if(Map[newNode.x]==0)
        {
            Map[newNode.x]=newNode.sum;
            if(newNode.sum>=100000) return;
            if(newNode.x!=0) Q.push(newNode);
        }
        newNode.x=(8*tmp.x+7)%Mod;
        newNode.sum=tmp.sum+1;
        if(Map[newNode.x]==0)
        {
            Map[newNode.x]=newNode.sum;
            if(newNode.sum>=100000) return;
            if(newNode.x!=0) Q.push(newNode);
        }
    }
    return ;
}
int main()
{
    long long n;
    cin>>n;
    if(n%Mod==0)
    {
        cout<<"0"<<endl;
        return 0;
    }
    bfs(n);
    if(Map[0]==0) cout<<"-1"<<endl;
    else cout<<Map[0]<<endl;
    return 0;
}

	#include <iostream>



	#include<bits/stdc++.h>



	#include<queue>



	#include <map>



	#define mod 1000000007LL



	using namespace std;



	//int vis[200000000]={0};



	int main()



	{   



	  map<long long,int> vis;



	queue<long long >q;



	



	int   n;



	



	



	



	long long xx;



	 



	while(cin>>n)



	{   



	int count=0;



	int ok=0;



	vis.clear();



	q.push(n);



	vis[n]=1;



	while(!q.empty())



	{



	long long a=q.front();



	q.pop();



	if(a==0){ok=1;count=vis[a];break;}



	if(vis[a]>100000) continue;



	xx=(4*a+3)%mod;



	if(!vis[xx])



	{



	q.push(xx);



	vis[xx]=vis[a]+1;



	}



	 



	xx=(8*a+7)%mod;



	 if(!vis[xx])



	{



	q.push(xx);



	vis[xx]=vis[a]+1;



	}



	



	



	



	



	}



	



	if(ok)cout<<count-1<<endl;



	else cout<<-1<<endl;



	



	



	



	}



	



	



	



	



	



	



	



	return 0;



	}

速度不快但是思路简单。

4x + 3等于做了两次2x + 1， 8x + 7做了三次。

从起点开始令x0 = 2*x0 + 1，统计做了多少次2x + 1后模1000000007等于0

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <map> 
#include <queue>
using namespace std;
typedef long long ll;

const int mod=1e9+7;

int main(){
    int n;
    while(~scanf("%d",&n)){
        int times=4;
        int ans=100001;
        for(int i=1;i<=300000;++i){
            int x=((long long)(n)*times+times-1)%mod;
            if(x==0){
                ans=(i+1)/3+((i+1)%3?1:0);
                break;
            }
            times=times*2%mod;
        }
        printf("%d\n",ans>100000?-1:ans);
    }
    return 0;
}

x=x+1;
x=(x*2)%1000000007;
x=(x*2)%1000000007;
x=(x+1000000006)%1000000007;

#include<cstdio>
int x87(int x, int x43){
    if(x==1000000006)return 100005;    //永远都差1步吃到草的
    int count=0;
    while(x43>0 && x%1000000007!=0){
        x++;
        x=(x*2)%1000000007;
        x=(x*2)%1000000007;
        x=(x+1000000006)%1000000007;
        count++;
        x43--;
    }
    while(x%1000000007!=0){
        x++;
        x=(x*2)%1000000007;
        x=(x*2)%1000000007;
        x=(x*2)%1000000007;
        x=(x+1000000006)%1000000007;
        count++;
        if(count>100000)return 100005;    //次数用完，吃不到
    }
    return count;
}
int main(){
    int x,f1=0,f2=0,f3=0,res=0;
    scanf("%d",&x);
    f1=x87(x,0);
    f2=x87(x,1);
    f3=x87(x,2);
    if(f1<f2)res=f1;
    else res=f2;
    if(f3<res)res=f3;
    if(res>100004)printf("-1\n");
    else printf("%d\n",res);
    return 0;
}