企业官网建设流程全解析

P1635 跳跃

网页链接

P1635 跳跃

题目背景

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

题目描述

青蛙小 C 听说 NOIP 要办周年庆比赛，兴冲冲得来到了 Z 市，初始时他在坐标x 0 x_0x0​处，小 C 是一只善于跳跃的青蛙，若当前他处在坐标x xx处，每一次跳跃，他可以跳到4 x + 3 4x+34x+3或8 x + 7 8x+78x+7处，且由于体力原因，他最多能跳100000 100000100000次。

根据 Z 市的传说，坐标位置为10 9 + 7 10^9+7109+7的整数倍的位置（如10 9 + 7 , 2 × 10 9 + 14 10^9+7,2\times 10^9+14109+7,2×109+14）可以传送到 YZOJ。

小 C 想知道，最少跳几次能传送到 YZOJ。

输入格式

输入的第一行包含一个整数x 0 x_0x0​表示青蛙的初始位置，保证x 0 x_0x0​在的范围在[ 1 , 10 9 + 6 ] [1,10^9+6][1,109+6]。

输出格式

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

输入输出样例 #1

输入 #1

125000000

输出 #1

1

解题思路

本题是数学变换与同余求解问题。青蛙每次跳跃可看作对当前位置施加两种线性变换之一，目标位置是10 9 + 7 10^9+7109+7的整数倍。通过将两种跳跃统一为更小的基本变换，并利用模运算将目标转化为使基本变换迭代后余数为0 00，可以高效地求出最少跳跃次数。

1. 问题等价转化

• 记M = 10 9 + 7 M = 10^9+7M=109+7。
• 定义基本变换f ( x ) = 2 x + 1 f(x) = 2x + 1f(x)=2x+1。
• 一次跳跃4 x + 3 4x+34x+3相当于连续执行两次f ff：
  f ( f ( x ) ) = 2 ( 2 x + 1 ) + 1 = 4 x + 3 f(f(x)) = 2(2x+1)+1 = 4x+3f(f(x))=2(2x+1)+1=4x+3
• 一次跳跃8 x + 7 8x+78x+7相当于连续执行三次f ff：
  f ( f ( f ( x ) ) ) = 8 x + 7 f(f(f(x))) = 8x+7f(f(f(x)))=8x+7
• 目标位置是M MM的整数倍，即最终坐标对M MM取模为0 00。
  因此问题转化为：找到最小的非负整数k kk，使得
  f k ( x 0 ) ≡ 0 ( m o d M ) f^k(x_0) \equiv 0 \pmod Mfk(x0​)≡0(modM)
  其中f k f^kfk表示f ff迭代k kk次。

2. 求解最少基本变换次数

• 由于M MM是质数，且x 0 x_0x0​范围在[ 1 , M − 1 ] [1, M-1][1,M−1]，可以直接从x 0 x_0x0​开始不断应用f ff（即a ← ( 2 a + 1 ) m o d M a \gets (2a+1) \bmod Ma←(2a+1)modM），直到a = 0 a=0a=0。
• 每应用一次f ff就对应一个基本步，记录总次数i ii。
• 因为一次跳跃最多对应3 33次基本步，青蛙最多跳10 5 10^5105次，所以基本步数最多只需要检查3 × 10 5 + 10 3\times 10^5 + 103×105+10次。若在该范围内仍不能使余数为0 00，则说明10 5 10^5105步内无法到达目标。

3. 将基本步数换算为最少跳跃次数

• 已知需要i ii次基本步。
• 每次跳跃可以使用两种“步长”：
  • 4 x + 3 4x+34x+3：消耗2 22次基本步；
  • 8 x + 7 8x+78x+7：消耗3 33次基本步。
• 为了用最少的跳跃次数凑够i ii次基本步，优先使用消耗3 33次基本步的跳跃。
  • 若i m o d 3 = 0 i \bmod 3 = 0imod3=0，则全部用8 x + 7 8x+78x+7，跳跃次数为i / 3 i/3i/3。
  • 若i m o d 3 = 1 i \bmod 3 = 1imod3=1或2 22，则用⌊ i / 3 ⌋ \lfloor i/3 \rfloor⌊i/3⌋次8 x + 7 8x+78x+7和一次4 x + 3 4x+34x+3（当余数为2 22时恰好弥补；余数为1 11时多出一次基本步，但跳跃次数仍为⌊ i / 3 ⌋ + 1 \lfloor i/3 \rfloor + 1⌊i/3⌋+1）。
    因此最少跳跃次数统一为⌈ i / 3 ⌉ \lceil i/3 \rceil⌈i/3⌉。

4. 算法步骤

1. 读入初始位置x 0 x_0x0​。
2. 令a = x 0 a = x_0a=x0​，i = 0 i = 0i=0。
3. 循环执行a = ( 2 a + 1 ) m o d M a = (2a + 1) \bmod Ma=(2a+1)modM，i = i + 1 i = i + 1i=i+1，直到a = 0 a = 0a=0或i > 3 × 10 5 + 10 i > 3\times 10^5 + 10i>3×105+10。
4. 若i > 3 × 10 5 i > 3\times 10^5i>3×105，说明无法在10 5 10^5105步内到达，输出− 1 -1−1。
5. 否则计算a n s = ⌈ i / 3 ⌉ = ( i + 2 ) / 3 ans = \lceil i/3 \rceil = (i+2)/3ans=⌈i/3⌉=(i+2)/3整数除法。
6. 若a n s > 10 5 ans > 10^5ans>105，输出− 1 -1−1；否则输出a n s ansans。

5. 复杂度分析

• 时间复杂度：最坏循环3 × 10 5 3\times 10^53×105次，每次O ( 1 ) O(1)O(1)，总复杂度O ( 10 5 ) O(10^5)O(105)，足够快。
• 空间复杂度：仅使用几个变量，O ( 1 ) O(1)O(1)。

总结

将两种跳跃统一为基本变换f ( x ) = 2 x + 1 f(x)=2x+1f(x)=2x+1，把目标转化为模M MM意义下使f ff迭代到0 00。求出所需最少基本步数后，再根据步长2 22和3 33的组合转换为最少跳跃次数。整个过程利用了模运算和线性变换的性质，简洁高效。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll LIM=100000;ll n,i,a,ans;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld",&n);for(i=0,a=n;i<=LIM*3+10;a=((a<<1)+1)%mod,i++)if(a==0)break;if(i%3==0)ans=i/3;if(i%3==1||i%3==2)ans=i/3+1;if(ans>LIM)ans=-1;printf("%lld\n",ans);return0;}