P1635跳跃（题解）

· · 题解

P1635跳跃（题解）

解题方法：

  1. 观察法。
  2. 简单数论。

    解题思路：

观察到4x+3=2(2x+1)+1以及8x+7=2(2(2x+1)+1)+1
所以可以把x->2x+1当成一个基本变化
则x->4x+3是两个基本变化，x->8x+7是三个基本变化
所以可以模拟一个基本变化
当基本变化次数大于300005是结束迭代
因为要使两个变化之和最小，所以尽量多用x->8x+7

  1. 当基本变化次数%3==0，都用x->8x+7，总次数=基本变化次数/3
  2. 当基本变化次数%3==1，用两个x->4x+3，剩下用x->8x+7，总次数=基本变化次数/3+1
  3. 当基本变化次数%3==2，用一个x->4x+3，剩下用x->8x+7，总次数=基本变化次数/3+1

    PS：

我爱压行！！！

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;    //模数
const ll MAX=100000;    //最大跳跃次数
ll n,i,x,ans;
int main()
{
    scanf("%lld",&n);
    for(i=0,x=n;i<=MAX*3+10;x=((x<<1)+1)%MOD,i++) if(x==0) break;   //求基本变化次数
    if(i%3==0) ans=i/3;     //求总次数
    if(i%3==1||i%3==2) ans=i/3+1;
    if(ans>MAX) ans=-1;     //判断能否到达
    printf("%lld\n",ans);
    return 0;
}