题目：

题目背景

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(m00000007==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; }

转载于:https://www.cnblogs.com/vercont/p/10210083.html

相关资源：JAVA上百实例源码以及开源项目