题目：

题目背景

NOIP即将迎来周年华诞。在这一个春秋的历程里，NOIP领导全国oier，建设高效、稳定、快捷、开放的社会主义现代化OI。在新的一年里，YZOJ将再接再厉，积极探寻成长之路，更好地为广大oier服务。

题目描述

青蛙小C听说NOIP要办周年庆比赛，兴冲冲得来到了Z市，初始时他在坐标x0处，小C是一只善于跳跃的青蛙，若当前他处在坐标x处，每一次跳跃，他可以跳到 $4x+3$4x+3或 $8x+7$8x+7处，且由于体力原因，他最多能跳 $100000$100000次。根据Z市的传说，坐标位置为 $1000000007$1000000007的整数倍的位置(如 $1000000007$1000000007、 $2000000014$2000000014)可以传送到YZOJ。小C想知道，最少跳几次能传送到YZOJ。

输入输出格式

输入格式：

输入的第一行包含一个整数x0表示青蛙的初始位置，保证x0在的范围在 $[1,1000000006]$[1,1000000006]。

输出格式：

输出一个整数，表示最少所需步数，若在 $100000$100000步内还无法传送到 $YZOJ$YZOJ，则输出 $-1$−1。

分析：

显然，这一看就是一道数学题

那么我们怎么考虑呢？

如果你细心一点就会发现：

$4x+3=2\ast (2x+1)+1$4x+3=2∗(2x+1)+1

$8x+7=2\ast (2\ast (2x+1)+1)+1$8x+7=2∗(2∗(2x+1)+1)+1

那么不就是说，只需要计算与2x+1有关的步数，然后推导普遍规律就行。

计算有几次2x+1的过程太简单，等会直接看代码就行。下面分析处理结果的方法。

再跳回两个式子：

$4x+3=2\ast (2x+1)+1$4x+3=2∗(2x+1)+1

$8x+7=2\ast (2\ast (2x+1)+1)+1$8x+7=2∗(2∗(2x+1)+1)+1

我们可以发现：最多的是由三个2x+1等构成（即8x+7），所以我们不妨考虑将结果先mod 3：

• % $3=0$3=0：那么就是一堆 $8x+7$8x+7(设为n个），输出 $answer/3;$answer/3;

• % $3=1$3=1:可以想成把本来的 $n$n个 $8x+7$8x+7从整好的多了一个 $2x+1$2x+1，所以只能拆出一个 $2x+1$2x+1，变成 $n-1$n−1个 $8x+7$8x+7和 $2$2个 $4x+3$4x+3.

• % $3=2$3=2：可以想成把本来的n个 $8x+7$8x+7从整好的多了两个 $2x+1$2x+1，所以n个 $8x+7$8x+7不用变，只是把多出的两个 $2x+1$2x+1合成一个 $4x+3$4x+3就行。

对了补充一句，因为首先是给出x，然后才能变成2x+1,4x+3，8x+7 . 等。所以所谓的三步其实是算上x变成2x+1的QAQ

然后归纳一下就行了，具体看代码：

#include<cstdio> 
using namespace std; 
const int mod=1000000007;//定义mod
int ans;
int search(int x)//递归部分，AC
{
	if(ans>=300100)//由于每次递归做的次数都很少，所以可以多做几次，避免误差
	{
		printf("-1");
		return 0;
	}
	int y=((x%mod)*2+1)%mod;
	ans++;
	if(y==0)//等于0就是达成了整数倍
	{//接下来就是归纳刚刚分析的内容，中间要判断答案是否在100000以内
		if(ans%3==0)
		{
			if(ans/3>100000)
			{
				printf("-1");
				return 0;
			}
			printf("%d",ans/3);
			return 0;
		}
		else
		{
			if(ans/3+1>100000)
			{
				printf("-1");
				return 0;
			}
			printf("%d",ans/3+1);
			return 0;
		}
	}
	else
	search(y);//继续走
	return 0;
}
int main()
{ 
	long long m; 
	scanf("%lld",&m);
	
	/*while(ans<=300000)//非递归部分，暂时没有AC
	{ 
		m=m*2+1;
		ans++;
		if(m%1000000007==0)
		{
			if(ans>100000)
			{
				printf("-1\n");
			}
			if(ans%3==0)
			printf("%d",ans/3);
			else
			{
				printf("%d",ans/3+1);
			}
			return 0;
		}
	} 
	printf("-1\n"); */
	search(m);
	return 0; 
}