洛谷 P1635 跳跃

题目：

题目背景

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

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

分析：

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

那么我们怎么考虑呢？

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

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

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

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

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

再跳回两个式子：

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

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

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

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

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

• %$3=2$：可以想成把本来的n个$8x+7$从整好的多了两个$2x+1$，所以n个$8x+7$不用变，只是把多出的两个$2x+1$合成一个$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; 
}